꽃길

국립공원에는 명소 $P$개와 명소를 잇는 양방향 등산로 $T$개가 있다. 공원 입구는 $0$번 명소이고, 가장 높은 봉우리는 $P-1$번 명소이다.

방문객은 입구에서 봉우리까지 최단 경로로 걷는다. 방문객마다 고르는 최단 경로가 달라서 최단 경로는 모두 누군가 지나간다. 입구에서 봉우리로 가는 최단 경로 중 하나에라도 놓인 등산로를 인기 등산로라고 한다.

관리인은 인기 등산로 양쪽에 꽃을 심는다. 길이가 $l$미터인 인기 등산로에는 꽃이 $2l$미터 필요하다. 필요한 꽃의 전체 길이를 구하라.

두 명소를 잇는 등산로가 여러 개일 수 있고, 시작 명소와 끝 명소가 같은 등산로도 있을 수 있다. 등산로는 하나씩 따로 세고, 인기 등산로는 최단 경로 몇 개에 놓이든 한 번만 센다. 입구에서 봉우리로 가는 경로는 반드시 하나 이상 있다.

첫째 줄에 정수 $P$와 $T$가 주어진다.

다음 $T$개 줄에는 정수 $p_1$, $p_2$, $l$이 주어진다. 길이가 $l$미터인 양방향 등산로가 $p_1$번 명소와 $p_2$번 명소를 잇는다는 뜻이고, 두 명소가 같을 수도 있다.

같은 줄의 정수는 공백 하나로 구분한다.

필요한 꽃의 전체 길이를 미터 단위 정수 하나로 한 줄에 출력한다.

• $2 \le P \le 10000$, 명소의 개수
• $1 \le T \le 250000$, 등산로의 개수
• $1 \le l \le 1000$, 등산로의 길이
• $0 \le p_1, p_2 \le P-1$