매주 주말 학교가 끝나면 학원에 가야 하는 시우는 반복되는 일상에 싫증이 나기 시작했다. 

이에서 벗어나고자 결국 pc방에 가야겠다는 결심을 하게 되었다!

시우의 집과 학원 근처에는 총 n개의 건물이 있고, 각 건물 사이로 이동하는 ‘길’은 총 m개 존재한다. 

모든 경우에 대해 n개의 건물들 중 1번째 건물은 시우의 집이고, 2번째 건물은 시우가 다니는 학원이며, 3~7번째 건물은 근처에 위치한 pc방 5개이다.

시우는 학원 수업은 안 듣더라도 시험공부는 해야 한다는 것을 알기 때문에 학원을 한 번은 들러 교재를 받아야 한다.

또한 모든 존재하는 ‘길’에 대해 ‘위험도’가 존재하는데, 이는 이 ‘길’을 통해 이동할 때 학원 선생님이나 부모님, 또는 친구들에게 걸릴 수 있는 정도를 뜻한다. 

시우는 최대한 은밀하게, 아무에게도 알려지지 않도록 pc방을 가고 싶어하기 때문에 이동하는 경로의 모든 ‘위험도’의 합을 최소화하려고 한다.

요약하자면, 시우는 집에서 나와서 근처에 있는 5개의 pc방 중 하나와 학원을 거친 후, 다시 집으로 들어오는 경로 중에서 ‘위험도’의 합이 최소인 것을 찾고 싶어한다.

시우를 도와주자.

모든 계산은 int 범위 내에서 일어난다.

첫 줄에는 시우의 집과 학원 근처에 있는 건물의 수 n과 ‘길’의 수 m이 입력된다. (7 <= n <= 10000), (6 <= m <= 10000)

두 번째 줄부터 m+1번째 줄에는 수 a, b, c가 입력되는데, 이는 a번째 건물과 b번째 건물 사이에 길이 존재하고, 그 길의 위험도가 c임을 의미한다.

시우가 갈 수 있는 모든 경로들 중 위험도가 가장 작은 경로의 위험도를 출력한다.

만약 어느 경우에도 경로가 존재하지 않는다면 –1을 출력한다.