Expected Path Length in a Forgotten Maze

You are trapped in a mysterious maze. Before the forgetfulness skill was activated, you memorized the layout of the maze: there are n rooms that are all connected, and there are exactly n bidirectional roads connecting them. In other words, the maze forms a connected graph with exactly one cycle (i.e. a unicyclic graph). Moreover, there is no road connecting a room to itself and no duplicate roads between any two rooms.

After the skill is cast you forget your current location and the exit room (both are chosen uniformly at random among the n rooms, with the starting room and the exit room guaranteed to be different). However, you still have a rough map that tells you for each road which two rooms it connects and its length. To pass to the next level you will travel along a route that does not traverse any road more than once. Since there may be more than one such route from your current room to the exit room, you will choose one of them uniformly at random.

Your task is to compute the expected length of the route you will travel. To avoid precision issues, output the answer modulo 19260817. Note that if there are two possible routes between two rooms on the cycle, the expected length is the arithmetic mean of the two lengths. In fact, for any two distinct rooms on the cycle the two available path‐lengths always sum up to the total length of the cycle; hence, the expected distance between any two distinct cycle rooms is exactly \(\frac{R}{2}\), where \(R\) is the sum of all the road lengths on the cycle.

More formally, if \(L(s,t)\) is the length of a route from room \(s\) to room \(t\) (taking the unique tree path when the pair is not both on the cycle and, if both are on the cycle, taking the average of the two simple path lengths) and the pair \((s,t)\) is chosen uniformly at random from all \(n(n-1)\) ordered pairs of distinct rooms, then you are to compute \[ E = \frac{1}{n(n-1)} \sum_{s\neq t} L(s,t) \pmod{19260817}. \]

Input Format: The first line contains an integer \(n\) denoting the number of rooms. Each of the following \(n\) lines contains three integers \(u, v, d\) meaning that there is a bidirectional road of length \(d\) connecting room \(u\) and room \(v\).

Output Format: Output a single integer which is the value of \(E\) modulo 19260817.

inputFormat

The first line contains an integer \(n\) (3 ≤ \(n\) ≤ 10⁵), representing the number of rooms. Each of the next \(n\) lines contains three integers \(u\), \(v\) and \(d\) (1 ≤ \(u,v\) ≤ \(n\), 1 ≤ \(d\) ≤ 10⁹), indicating there is a bidirectional road between rooms \(u\) and \(v\) with length \(d\). It is guaranteed that the graph is connected, contains exactly \(n\) edges, and there are no self‐loops or multiple edges between the same pair of vertices.

outputFormat

Output a single integer: the expected route length (as described) modulo 19260817.

sample

3
1 2 1
2 3 2
3 1 3

14354774