// infoarena: problema/bellmanford //
#include <fstream>
#include <vector>
#include <set>
using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int MAXN = 50010;
const int MAXM = 250010;

vector<int> g[MAXN];
set<int> q;
int i,j,n,m,x,y,z,pred[MAXN],s[MAXM],e[MAXM],l[MAXM],d[MAXN];

int main()
{
    in>>n>>m;

    for(i=1; i<=m; i++)
    {
        in>>x>>y>>z;
        g[x].push_back(i);
        s[i] = x;
        e[i] = y;
        l[i] = z;
    }

    for(i=2; i<=n; i++)
        d[i] = 1<<29;

    for(i=1; i<=m; i++)
        q.insert(i);

    for(i=2; i<=n; i++)
        for(set<int>::iterator it=q.begin(); it!=q.end(); it++)
            if(l[*it] + d[s[*it]] < d[e[*it]])
            {
                d[e[*it]] = l[*it] + d[s[*it]];
                pred[e[*it]] = s[*it];
            }
            else
            {
                q.erase(it);
            }

    for(i=1; i<=m; i++)
        if(l[i] + d[s[i]] < d[e[i]])
        {
            out<<"Ciclu negativ!";
            return 0;
        }

    for(i=2; i<=n; i++)
        out<<d[i]<<' ';

    return 0;
}