#1698 돌고 돌고 돌고 HARD

36  2 s   128 MB  

Description

게으름국의 각 도시에는 경찰차가 한 대씩 배치되어 있다. 경찰차는 하루에 한 번씩 순찰을 도는데, 순찰 경로는 반드시 출발하는 도시에서 이동이 가능한 다른 도시를 거쳐서 다시 출발한 도시로 돌아오도록 한다. 게으름국의 경찰들은 국가 이름처럼 게을러서 순찰을 가능한 빨리 끝내고 싶어 하기 때문에 순찰 경로를 최대한 짧게 해야한다.

게으름국의 도로 정보가 주어질 때, 각 도시에 배치된 경찰차가 순찰하는 경로의 거리를 알아내자.

Input

전체 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 도시의 개수를 나타내는 정수 N과 도로의 개수를 나타내는 정수 M이 주어진다. 각 테스트 케이스의 두 번째 줄부터 M개 줄에 걸쳐 각 도로의 정보가 하나씩 주어진다. 하나의 도로 정보는 출발 도시, 도착 도시, 거리를 나타내는 세 개의 정수 Vi, Ui, Di로 표현된다. 도로는 모두 일방 통행이다.

모든 도시에는 반드시 하나 이상의 순찰 경로가 존재한다.

제약조건

Output

각 테스트 케이스에 대해, 1번 도시부터 N번 도시까지 각 도시에 배치된 경찰차가 순찰하는 경로의 길이를 한 줄에 출력한다.

Sample Input

Sample Output

2
4 6
1 2 1
2 1 2
2 4 3
3 2 4
4 1 2
4 3 5
5 6
1 2 2
2 3 3
2 4 1
3 1 5
4 5 4
5 1 2
3 3 12 6
9 9 10 9 9

HINT

첫 번째 테스트 케이스에서 1번, 2번 도시의 경찰차는 1->2->1 로 이어지는 경로로 순찰을 돌고, 4번 도시의 경찰차는 4->1->2->4 로 이어지는 경로로, 3번 도시의 경찰차는 3->2->4->3 로 이어지는 경로로 순찰을 돈다.

Source

RUN Programming Contest, February 2011