#include <fstream>
#include <vector>
#include <deque>
#include <bitset>
#define N 50003
#define INF 99999999
using namespace std;
vector < int > v[N],c[N];
deque < int > q;
int n,e[N];
short k[N];
bitset < N > u;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");

int main()
{
    int m,x,y,z,i;
    in>>n>>m;
    while(m--)
    {
        in>>x>>y>>z;
        v[x].push_back(y);
        c[x].push_back(z);
    }
    for(i=1;i<=n;i++)
        e[i]=INF;
    e[1]=0;
    q.push_back(1);
    while(!q.empty())
    {
        for(i=0;i<v[q[0]].size();i++)
            if(e[v[q[0]][i]]>e[q[0]]+c[q[0]][i])
            {
               e[v[q[0]][i]]=e[q[0]]+c[q[0]][i];
                if(u[v[q[0]][i]]==0)
                {
                   q.push_back(v[q[0]][i]);
                   u[v[q[0]][i]]=1;
                }
            }
        u[q[0]]=0;
        k[q[0]]++;
        if(k[q[0]]>=n)
        {
            out<<"Ciclu negativ!\n";
            return 0;
        }
        q.pop_front();
    }
    for(i=2;i<=n;i++)
        out<<e[i]<<' ';
    return 0;
}