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

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

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

vector<int> g[MAXN];
queue<int> q;
int i,j,n,m,x,y,z,pred[MAXN],s[MAXM],e[MAXM],l[MAXM],d[MAXN],count[MAXN],nod;
bool in_queue[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;

    q.push(1);
    in_queue[1] = true;

    while(!q.empty())
    {
        nod = q.front(); q.pop();
        in_queue[nod] = false;

        for(vector<int>::iterator it=g[nod].begin(); it!=g[nod].end(); it++)
            if(l[*it] + d[s[*it]] < d[e[*it]])
            {
                d[e[*it]] = l[*it] + d[s[*it]];
                pred[e[*it]] = s[*it];
                if(!in_queue[e[*it]])
                {
                    q.push(e[*it]);
                    count[e[*it]] ++;
                    in_queue[e[*it]] = true;
                    if(count[e[*it]] >= n)
                    {
                        out<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
    }

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

    return 0;
}