Minimum Time to Notify All Computers

You are given a network of N computers connected by bidirectional links. Each link is described by a triplet \( (u, v, t) \), meaning that it takes \( t \) time units to transmit a message between computers \( u \) and \( v \). The network is guaranteed to form a tree (i.e. a connected acyclic graph).

The main server is computer 1. When a message is sent from the main server, it will propagate throughout the network along the unique paths. The time required to notify all computers is equal to the maximum time it takes for the message to reach any computer from the main server.

Formally, if \( d(1, i) \) represents the time delay from computer 1 to computer \( i \), you are required to compute

[ \max_{1 \le i \le N} d(1, i), ]

where the delays \( d(1, i) \) are computed as the sum of transmission times along the unique path from node 1 to node \( i \). Output this maximum delay.

inputFormat

The input is given via standard input in the following format:

N E
u1 v1 t1
u2 v2 t2
... 
uE vE tE

Where:

• N is the number of computers.
• E is the number of edges (for a tree, \( E = N - 1 \); note that when \( N = 1 \), \( E \) is 0).
• Each of the next E lines contains three integers representing an edge (u, v, t) as described above.

outputFormat

Output a single integer via standard output which is the minimum time needed for the main server (node 1) to notify all computers.

## sample

1 0

0