34233번 - 그래프 탐험하기

문제

태우는 정점이 $N$개 있는 가중치 있는 양방향 그래프를 탐험하기 위해 계획을 세우고 있다. 태우는 속지의 앞면만 사용하는 수첩과 형광펜을 가지고 있고, 1ドル$번 정점에서 탐험을 시작한다.

그래프를 탐험할 때는, 다음 방법으로 탐험한다:

1. 1ドル$번 정점에서 탐험을 시작할 때, 수첩의 첫 페이지에 1ドル$이 적혀 있고 다른 모든 페이지에는 아무 것도 적혀 있지 않다.
2. 현재 위치한 정점과 인접한 정점 중 수첩에 기록한 적 없는 모든 정점에 대해, 번호가 작은 순서대로 다음을 수행한다.
   • 정점의 번호를 수첩의 빈 페이지 중 첫 페이지와 가장 가까운 페이지에 기록한다.
   • 현재 위치한 정점과 인접한 정점 사이 간선을 형광펜으로 표시한다.
3. 수첩의 첫 페이지에 적힌 번호의 정점으로 이동한 후 첫 페이지를 찢어서 폐기한다. 이때, 형광펜으로 표시한 간선만을 이용하는 경로 중 최단 경로로 이동해야 한다.
4. 수첩의 모든 페이지가 빌 때까지 2번과 3번을 반복한다.
5. 수첩의 모든 페이지가 비었다면, 현재 위치한 정점에서 형광펜으로 표시한 간선만을 이용하는 경로 중 최단 경로로 1ドル$번 정점으로 돌아온다.

수첩의 페이지 수는 $N$보다 크며, 형광펜 속 잉크는 무한하다. 이러한 방식으로 그래프를 탐험할 때, 지나는 간선의 가중치의 합은 얼마일까?

입력

첫째 줄에 정점의 수 $N$과 간선의 수 $M$이 공백으로 구분되어 주어진다. (3ドル\leq N\leq 1,円 000$; $N-1\leq M\leq\min\left( {{N(N-1)}\over 2} ,100,円 000 \right)$)

둘째 줄부터 $M$개 줄에 걸쳐 인접한 두 정점의 번호와 가중치 $u,v,w$가 공백으로 구분되어 주어진다. (1ドル\leq u,v\leq N$; $u\neq v$; 1ドル\leq w\leq 1,円 000,円 000$)

서로 다른 두 정점을 연결하는 간선은 0ドル$개 또는 1ドル$개이며, 입력으로 주어지는 간선은 양방향이다.

1ドル$번 정점에서 시작해 $N$개 정점에 모두 도달 가능한 경우만 입력으로 주어진다.

출력

첫째 줄에 모든 간선에 대해, (간선을 거쳐간 횟수 $\times$ 간선의 가중치)의 합을 출력한다.

제한

힌트