Little Monk's interviews
Tag(s):

## Graph Theory, Greedy, Medium, Minimum Spanning Tree

Problem
Editorial
Analytics

Little Monk wants to get a job offer during placement as soon as possible. To increase his chances of getting a job, he wants to give as many interviews at as many different companies as possible. There are N rooms, which are labeled from $1$ to N, and in each room a different company is doing its interview process. Between these N rooms, we have M paths which guarantee the fact that the Monk can reach any room from any given room he's in. Every M path takes some T time to travel between two rooms.

Importantly, he wants to maximize his travel time so he can revise his concepts while traveling. Since he's busy preparing for his interviews, help him maximize his travel time so he can prepare for his interviews. Obviously, there will be no cycle allowed in this graph. Since Monk is also enlightened, once he has traveled on a particular path, he takes $0$ units of time to travel on it again.

Input format:
The first line contains an integer TC, which denotes the number of test cases. The next line contains two integers, N and M, denoting the number of rooms and number of paths. The next M lines contain three integers U, V, and T, where U and V denote the two edges being joined, and T denoting the time taken to travel between U and V.

Output format:
Print the maximum time obtained by Monk to revise his concepts to each test case in a new line.

Constraints:
$1$ ≤ Test Cases ≤ $10$
$1$ ≤ N ≤ $10^5$
$1$ ≤ M ≤ $10^6$
$1$ ≤ W ≤ $10^3$

Note: The test data contains a lot of I/O operations, it is thus recommended to use faster input / output mechanisms.

SAMPLE INPUT
1
4 6
1 2 10
1 3 20
1 4 30
2 3 40
2 4 50
3 4 60

SAMPLE OUTPUT
140

Explanation

Here Monk will go from 4->1, then comes back to 4, then 4->2, then comes back to 4 and then 4 -> 3.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeMonk (Greedy Technique)

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Greedy Algorithms
• Algorithms > Greedy Algorithms
• Algorithms > Greedy Algorithms
• Math > Basic Math