#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
#define inf 696969
#define NMAX 50001
using namespace std;

int viz[50001],prec[50001],d[50001];

typedef struct{
    int v;
    int value;
}node;

bool operator<(node a, node b)
{
    return (a.value > b.value);
}

vector<node> cost[50001];
priority_queue<node> q;

void drum(int x, int vf)
{
    if(vf!=x)
        drum(x,prec[vf]);
    cout<<vf<<" ";
}

/* solutie nu tocmai eficienta...
int bellman_ford (int x0, int n)
{
    int i,j;

    for(i=0;i<cost[x0].size();i++)
    {
        d[cost[x0][i].v] = cost[x0][i].value;
        prec[cost[x0][i].v] = x0;
    }

    for(i=1;i<=n;i++)
    {
        if(d[i]==0)
            d[i]=inf;
    }

    d[x0]=0;

    for(int k=0;k<=n-2;k++)
    {
        for(i=1;i<=n;i++)//u e i si v e cost[i][j].v cu cost intre muchii cost[i][j].value
            for(j=0;j<cost[i].size();j++)
            {
                if (d[cost[i][j].v] > d[i] +cost[i][j].value)
                {
                    d[cost[i][j].v] = d[i] +cost[i][j].value;
                    prec[cost[i][j].v] = i;
                }
            }
    }

    for(i=1;i<=n;i++)//u e i si v e cost[i][j].v cu cost intre muchii cost[i][j].value
            for(j=0;j<cost[i].size();j++)
            {
                if (d[cost[i][j].v] > d[i] +cost[i][j].value)
                    return 0;
            }
    return 1;
}*/

int nodes[50001];

int bellman_ford (int x0, int n)
{
    int i,j;
    queue<int> q;
    bool in_q[50001] = {false};

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

    d[x0]=0;
    q.push(x0);
    in_q[x0] = true;

    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        in_q[x] = false;

        for(j=0;j<cost[x].size();j++)
        {
            if(d[x] < inf)
            {
                if (d[cost[x][j].v] > d[x] + cost[x][j].value)
                {
                    d[cost[x][j].v] = d[i] + cost[x][j].value;
                    prec[cost[x][j].v] = x;

                    if (!in_q[cost[x][j].v])
                    {
                        if (nodes[cost[x][j].v] > n)
                        {
                            return 0;
                        }
                        else
                        {
                            q.push(cost[x][j].v);
                            in_q[cost[x][j].v] = true;

                        }
                    }
                }
            }
        }
    }
    return 1;
}

int main()
{
    int m,n,i,j,x,y,val;
    fstream f, out;
    f.open("bellmanford.in",ios::in);
    out.open("bellmanford.out",ios::out);
    f>>n>>m;

    for(i=1;i<=m;i++)
    {
        f>>x>>y>>val;
        node nod;
        nod.v = y;
        nod.value=val;
        cost[x].push_back(nod);
    }

    /*for(i=1;i<=n;i++)
    {
        cout<<i<<": ";
        for(j=0;j<cost[i].size();j++)
            cout<<"("<<cost[i][j].v<<" "<<cost[i][j].value<<") ";
        cout<<endl;
    }*/

    int res = bellman_ford(1,n);

    if (res == 0)
    {
        out<<"Ciclu negativ!";
        return 0;
    }

    for(i=2;i<=n;i++)
        if(d[i]<inf)
        {
            out<<d[i]<<" ";
            //drum(x0,i);
        }
        else
            out<<"0 ";

}