#include<fstream>
#include<vector>
#include<queue>
using namespace std;

struct nod
{
    int vecin,cost;
};

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

const int oo=1<<30;
const int NMAX=50005;

int n,m;
vector<nod>v[NMAX];
int dist[NMAX],frecv[NMAX];
queue<nod>Q;

inline void Citire()
{
    int i,x;
    nod k;
    fin>>n>>m;
    for (i=1;i<=m;i++)
        {
            fin>>x>>k.vecin>>k.cost;
            v[x].push_back(k);
        }
    dist[1]=0;
    for (i=2;i<=n;i++) dist[i]=oo;
}

inline void Afisare()
{
    int i;
    for (i=2;i<=n;i++)
        if (dist[i]!=oo) fout<<dist[i]<<" ";
        else fout<<"0 ";
}

inline void BELLMANFORD()
{
    int x,costarico;
    bool test=0;
    nod k,kl;
    k.vecin=1;
    k.cost=0;
    Q.push(k);
    while (!Q.empty() && !test)
        {
            x=Q.front().vecin;
            costarico=Q.front().cost;
            Q.pop();
            frecv[x]++;
            if (frecv[x]<n)
                {if (costarico==dist[x])
                    {
                        for (vector<nod>::iterator it=v[x].begin();it!=v[x].end();it++)
                            {
                                kl=*it;
                                if (dist[kl.vecin]>dist[x]+kl.cost)
                                    {
                                        dist[kl.vecin]=dist[x]+kl.cost;
                                        k.vecin=kl.vecin;
                                        k.cost=dist[kl.vecin];
                                        Q.push(k);
                                    }
                            }
                    }
                }
            else test=1;
        }
    if (!test) Afisare();
    else fout<<"Ciclu negativ!\n";
}

int main()
{
    Citire();
    BELLMANFORD();
    return 0;
}