#include<fstream>
#include<vector>
#define INF 1000000000 
using namespace std; 
ifstream intrare("bellmanford.in");
ofstream iesire("bellmanford.out"); 
int n, cmin[50010], coada[500000], nrpus[50010]; 
vector<int>a[50010];
vector<int>cost[50010];
int main()
{
    int m, x, y, costv, i;
    intrare>>n>>m;
    for(i=1;i<=m;i++)
    {
        intrare>>x>>y>>costv;
        cost[x].push_back(costv);
        a[x].push_back(y);
    }
    for(i=1;i<=n;i++)
        cmin[i]=INF;
    cmin[1]=0;
	//bellman
    int inc, sf;
    inc=sf=1; coada[1]=1;
    while(inc<=sf)
    {
        x=coada[inc++];
        for(y=0;y<a[x].size();y++)
            if(cmin[x]+cost[x][y]<cmin[a[x][y]])
            {
                cmin[a[x][y]]=cmin[x]+cost[x][y];
                coada[++sf]=a[x][y];
                nrpus[a[x][y]]++;
                if(nrpus[a[x][y]]>=n)
                {
                    iesire<<"Ciclu negativ!";
                    break;
                }
            }
    }
    for(i=2;i<=n;i++)
        iesire<<cmin[i]<<' ';
    iesire<<'\n';
    iesire.close();
    return 0;
}