• [D] Bridge And Island Again

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • In order to strengthen the communication between the island, the government wants to convey goods from first island to Nth island. Now give you some bridges that can bear the maximum weight of goods.
    Can you calculate the maximum weight of goods that first island can convey at one time.

  • 输入
  • Input until EOF.
    First line will give you two integers N (4 <= N <= 100)(the id of islands are from 1 to N) and M (N - 1 <= M <= N * (N - 1) / 2), N means the number of islands, M means the number of bridges have be built.
    Next M lines, each line contains three integers x, y, and c (0 < c < 100), means there exists the maximum bear c from x to y (The maximum bear from x to y may be different from the maximum bear from y to x).
    For data.in, there may exist two bridges between two islands, and all islands will be linked by bridges.
  • 输出
  • Print the answer.
  • 样例输入
  • 4 6
    1 2 1
    1 3 1
    1 4 1
    2 3 2
    2 4 2
    3 4 2
    
  • 样例输出
  • 3
    
  • 提示
  • 来源
  • Hungar
  • 操作

显示春菜