#include <fstream>
#include <vector>
#include <queue>
#define punct pair<int,int>
#define x first
#define y second
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int N,M,i,S,d[100005],x,y,z,viz[100005];
queue<int> Q;
vector<punct> v[100005];
int main()
{
    f>>N>>M;
    while(M--)
        f>>x>>y>>z,v[x].push_back(make_pair(y,z));
    for(i=1;i<=N;++i)d[i]=1<<30;

    Q.push(1),d[1]=0;
    while(!Q.empty())
        {
            int cr=Q.front();Q.pop();
            if (viz[cr]==N)
                {g<<"Ciclu negativ!";return 0;}

            for (i=0;i<v[cr].size();++i)
                if (d[v[cr][i].x]>d[cr]+v[cr][i].y)
                    d[v[cr][i].x]=d[cr]+v[cr][i].y,++viz[v[cr][i].x],Q.push(v[cr][i].x);
        }
    for (i=2;i<=N;++i)
        g<<d[i]<<" ";





    return 0;
}