[USACO 2011 Mar S]Package Delivery

题号：NC24625
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

Farmer John must deliver a package to Farmer Dan, and is preparing to make his journey. To keep the peace, he gives a tasty treat to every cow that he meets along his way and, of course, FJ is so frugal that he would like to encounter as few cows as possible.

FJ has plotted a map of N (1 <= N <= 50,000) barns, connected by M (1 <= M <= 50,000) bi-directional cow paths, each with $C_i$ (0 <= $C_i$ <= 1,000) cows ambling along it. A cow path connects two distinct barns, $A_i$ and $B_i$ (1 <= $A_i$ <= N; 1 <= $B_i$ <= N; $A_i$ != $B_i$ ). Two barns may be directly connected by more than one path. He is currently located at barn 1, and Farmer Dan is located at barn N.

Consider the following map:

           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3

The best path for Farmer John to take is to go from 1 -> 2 -> 4 -> 5 -> 6, because it will cost him 1 + 0 + 3 + 1 = 5 treats.

Given FJ's map, what is the minimal number of treats that he should bring with him, given that he will feed each distinct cow he meets exactly one treat? He does not care about the length of his journey.

输入描述:

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Three space-separated integers: , , and

输出描述:

* Line 1: The minimum number of treats that FJ must bring

示例1

输入

复制

输出

复制