#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAXN 1e6

using namespace std;

int n, m;
int edge [ 1010] [ 1010];
int dist [ 1010];
int ans = MAXN;

int main ( )
{
    cin>> n>> m;
    for ( int i = 1; i <= n; i ++)
    {
        for ( int j = 1; j <= m; j ++)
        {
            edge [ i] [ j] = MAXN;
        }
        dist [ i] = MAXN;
    }
    for ( int i = 1; i <= m; i ++)
    {
        int a, b, c;
        cin>> a>> b>> c;
        edge [ a] [ b] = c;
    }

    for ( int i = 1; i <= n; i ++)
    {
        for ( int j = 1; j <= m; j ++)
        {
            dist [ i] = min ( dist [ i], edge [ i] [ j] + edge [ j] [ i]);
        }
    }

    for ( int i = 1; i <= n; i ++)
    {
        ans = min ( ans, dist [ i]);
    }
    printf ( "%d\n", ans);
    return 0;
}