#include <bits/stdc++.h>
#define inf 1<<30

using namespace std;

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

int n,m,G,drum[50005],hah[50005],ok=1;
bool viz[50005];

queue <int>q;
vector <pair<int,int> >L[50005];

void Citire()
{
    int x,y,c;

    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        L[x].push_back({y,c});
    }

}
inline void BellmanFordu()
{
    int el;
    ok=1;
    q.push(1);

    for(int i=2;i<=n;i++)
        drum[i]=inf;
    drum[1]=0;
    viz[1]=1;

    while(!q.empty() && ok==1)
    {

        el=q.front();
        q.pop();
        viz[el]=0;

        for(int i=0;i<L[el].size();i++)
        {
            int p=L[el][i].first;
            int cost=L[el][i].second;

            if(drum[p]>drum[el]+cost)
            {
                drum[p]=drum[el]+cost;

                if(!viz[p])
                {

                    if(hah[p]>n)
                        fout<<"Ciclu negativ!\n",ok=0;
                    else
                    {
                        viz[p]=1;
                        hah[p]++;
                        q.push(p);
                    }

                }
            }
        }
    }
    if(ok==1){
        for(int i=2;i<=n;i++)
            fout<<drum[i]<<" ";
        fout<<"\n";
    }
}
int main()
{
    Citire();
    BellmanFordu();
    return 0;
}