#include <bits/stdc++.h>
#define MAX 50000007
#define N 50007

using namespace std;


ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m;
bool ok;
vector<int>dist(N,MAX);
vector<int>ct(N,0);
vector <pair<int,int>>a[N];
queue<int> q;

void Citire()
{
    fin >> n >> m ;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        a[x].push_back( {c,y} );
    }
    fin.close();
}

void Update(int x)
{
    for(auto y:a[x])
        if( dist[y.second]>dist[x]+y.first )
        {
            ct[y.second]++;
            dist[y.second]=dist[x]+y.first;
            q.push(y.second);
            if( ct[y.second]>=n )ok=0;
        }
}

void Belman_Ford()
{
    dist[1]=0;
    q.push(1);
    ok=1;
    while( !q.empty() and ok)
    {
        int cur=q.front();
        q.pop();
        Update(cur);
    }
    if( !ok )
        fout << "Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout << dist[i] << " ";
}



int main()
{
    Citire();
    Belman_Ford();
    return 0;
}