#include <fstream>
#include <vector>
#include <queue>
#define oo 0x3f3f3f3f

using namespace std;

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

typedef  pair <int, int> PER;
vector <PER> G[50001];
int D[50001],P[50001],nr[500001];
bool V[50001];

int main()
{
    int N,m;
    fin>>N>>m;
    for(int i=1;i<=m;++i){
        int x,y,z;
        fin>>x>>y>>z;
        G[x].push_back(make_pair(y,z));
    }
    for(int i=0;i<=N;i++)
        {D[i]=oo;P[i]=0;V[i]=false;}
    V[1]=true;D[1]=0;
    queue<int>Q; Q.push(1);
    while(!Q.empty())
    {
        int nod=Q.front();
        V[nod]=false;
        vector<PER>::iterator i;
        for(i=G[nod].begin();i!=G[nod].end();++i)
        if (D[nod]+i->second<D[i->first])
        {
            D[i->first]=D[nod]+i->second;
            if(!V[i->first])
            {
                if(nr[i->first]>N)
                {
                    fout<<"Ciclu negativ!\n";
                    return 0;
                }
                Q.push(i->first);
                V[i->first]=true;
                ++nr[i->first];
            }
        }
        Q.pop();
    }
    for(int i=2;i<=N;i++)
        fout<<D[i]<<" ";
    return 0;
}