[白俊]1956/スポーツ

/*
 * Problem :: 1956 / 운동
 *
 * Kind :: Floyd-Warshall
 *
 * Insight
 * - 사이클이라...
 *   그래프에 존재하는 모든 사이클을 찾아봐야 하나?
 *   + 라고 생각하던 참에 도로 길이의 합이 가장 작은 사이클을 찾는거라면
 *     정점 i 에서 출발하여 i 로 돌아오는 최단거리를 찾는 것이고 (dp[i][i])
 *     모든 정점마다 이를 수행해야하며
 *     max(V)=400 이면 V^3 <= 64*10^6 으로 2초 이내에 충분히 가능할 것 같았다
 *     # 플로이드-와샬 알고리즘을 적용하면 될까?
 *       보통은 dp[i][i] 를 0 으로 초기화시켜주는데
 *       여기서는 INF 로 초기화시켜주면 되지 않을까?
 *       -> 네, 되었다고 합니다
 *
 * Point
 * - 플로이드-와샬로 사이클도 찾을 수 있구나
 */

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
#define INF (400*10000 + 1)

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int V, E;
    cin >> V >> E;
    int dp[V+1][V+1];
    fill(&dp[1][1], &dp[V][V+1], INF);
    for (int i=0; i<E; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dp[a][b] = c;
    }

    // Process
    for (int m=1; m<=V; m++) {
        for (int f=1; f<=V; f++) {
            for (int t=1; t<=V; t++) {
                if (dp[f][t] > dp[f][m] + dp[m][t]) {
                    dp[f][t] = dp[f][m] + dp[m][t];
                }
            }
        }
    }

    int ans = INF;
    for (int i=1; i<=V; i++) {
        ans = min(ans, dp[i][i]);
    }

    // Control : Output
    cout << ((ans == INF) ? -1 : ans) << endl;
}

// Helper Functions
/* None */