#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define INF 1<<30

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct nawd{int nod;int cost;};
vector <nawd> v[50002];
int n,m,i,c[50002],out[50002];bool ok,viz[50002],x;
void bfs(int entry)
{
    queue <int> q;
    q.push(entry);
    viz[entry]=true;
    while(!q.empty())
    {
       int fr=q.front(); q.pop();  viz[fr]=false;
       for(i=0;i<v[fr].size();i++)
       {
           if(c[fr]+v[fr][i].cost<c[v[fr][i].nod])
           {

                c[v[fr][i].nod]=c[fr]+v[fr][i].cost;out[fr]++;
                if(viz[v[fr][i].nod]==false)
                {
                    viz[v[fr][i].nod]=true;
                    q.push(v[fr][i].nod);
                }

            if(out[v[fr][i].nod]==(n-1))
            {
                   ok=true;
                    g<<"Ciclu negativ!";
                    break;

            }
           }
       }
    }

}
int main()
{   ok=false;
    f>>n>>m;
    c[1]=0;
    for(i=2;i<=n;i++)
    {
        c[i]=INF;
    }
    nawd w;
    for(i=1;i<=m;i++)
    {
        f>>x>>w.nod>>w.cost;
        v[x].push_back(w);
    }
    bfs(1);
    if(ok==false)
    {
        for(i=2;i<=n;i++)
            g<<c[i]<<" ";
    }
    return 0;
}