#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream is("bellmanford.in");
ofstream os("bellmanford.out");

#define INF 0x3f3f3f3f

vector<vector<pair<int, int>>> G;
vector<int> d, nr;
vector<bool> s;
int n, m, x, y, cost;
int ciclu;
queue<int> q;

void BF();

int main()
{
    is >> n >> m;
    G.resize(n+1);
    d = vector<int>( n + 1, INF );
    s = vector<bool>(n+1);
    nr = vector<int>(n+1);

    for ( int i = 1; i <= m; i++ )
    {
        is >> x >> y >> cost;
        G[x].push_back({y, cost});
    }
    BF();
    if ( ciclu == 1 )
        os << "";
    else
        for ( int i = 2; i <= n; i++ )
            os << d[i] << ' ';
    is.close();
    os.close();
    return 0;
}

void BF()
{
    q.push(1);
    s[1] = true;
    d[1] = 0;
    int k;
    while(!q.empty())
    {
        k = q.front();
        s[k] = false;
        q.pop();
        for ( const auto& y : G[k] )
            if ( d[y.first] > d[k] + y.second )
            {
                d[y.first] = d[k] + y.second;
                if( s[y.first] == false )
                {
                    nr[y.first]++;
                    if ( nr[y.first] == n )
                    {
                        ciclu = 1;
                        return;
                    }
                    s[y.first] = true;
                    q.push(y.first);
                }
            }
    }
}