提示: 欢迎访问OurACM平台。
Problem 1565 The Lightest Cycle

Accept: 60    Submit: 201
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Given a directed weighted graph who has at least three nodes, can you find the minimal directed weighted cycle with at least three nodes?

Input

The input contains multiple test cases.
Each test case :

  • In the first line there is two integer n - the number of nodes in the graph, m - the number of directed edges in the graph. (0 < n <= 100, 0 <= m <= n^2)
  • Then m lines follow, each line contains three integers i j k, which means that there is a directed edge coming from node i to node j with a weight of k (0 <= k < 2^15).
  • Output

    You should output a single line with a single integer presenting the weight of the cycle you have found or "-1" (without quotes) if there isn't any.

    Sample Input

    5 7 4 0 19 0 3 20 4 3 50 2 3 1 3 1 10 1 4 2 1 2 39

    Sample Output

    50

    Source

    FOJ月赛-2008年2月

    Submit  Back  Status  Discuss