시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 (추가 시간 없음) 1024 MB 42 9 8 40.000%

## 문제

You are given a simple connected undirected weighted graph $G$ with $N$ nodes and $M$ edges. Each node is numbered 1 through $N$.

A spanning tree of $G$ is a subgraph of $G$, which is a tree and connects all the vertices of $G$. The diameter of a tree is the length of the longest path among the paths between any two nodes in the tree. A minimum diameter spanning tree of $G$ is a spanning tree of $G$ that has a minimum diameter.

Write a program that finds any minimum diameter spanning tree.

## 입력

The first line of the input contains two integers $N$ ($2 \le N \le 500$) and $M$ ($N-1 \le M \le \frac{N(N-1)}{2}$).

Then $M$ lines follow: The $i$ ($1 \le i \le M$)-th line contains three space-separated integers $u_i$, $v_i$ and $l_i$ ($1 \le u_i, v_i \le N$, $1 \le l_i \le 10^9$); it describes a bidirectional edge connecting vertex $u_i$ and vertex $v_i$ with length $l_i$.

It is guaranteed that the given graph doesn't have any loops or multiple edges, and the graph is connected.

## 출력

In the first line, print the diameter of the minimum diameter spanning tree of $G$.

In the next $N-1$ lines, print the description of the edges in the minimum diameter spanning tree of $G$. The $j$ ($1 \le j \le N-1$)-th line should contain two space-separated integers $x_i$ and $y_i$ ($1 \le x_i,\ y_i \le N$); it describes a bidirectional edge connecting vertex $x_i$ and $y_i$.

If there are several possible answers, print any one of them.

## 예제 입력 1

3 3
1 2 1
2 3 1
3 1 1


## 예제 출력 1

2
1 2
3 1


## 예제 입력 2

6 7
1 2 10
2 3 20
1 3 30
3 4 1000
4 5 30
5 6 20
4 6 10


## 예제 출력 2

1060
3 4
6 4
5 6
2 3
1 2