#include<fstream>
#include<queue>
#include<vector>
#define pb push_back
#define mp make_pair
#define fiu first
#define cost second
#define INF 1<<30
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int i,n,m,x,y,z,d[50100],nr[50100];
vector<pair<int,int> >l[50100];
queue<int>q;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        l[x].pb(mp(y,z));
    }
    for(i=2;i<=n;++i)
    d[i]=INF;
    q.push(1);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        ++nr[x];
        if(nr[x]>n)
        {
            g<<"Ciclu negativ!\n";
            return 0;
        }
        for(vector<pair<int,int> >::iterator it=l[x].begin();it!=l[x].end();++it)
        if(d[x]+it->cost<d[it->fiu])
        {
            d[it->fiu]=d[x]+it->cost;
            q.push(it->fiu);
        }
    }
    for(i=2;i<=n;++i)
    g<<d[i]<<' ';
}