#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define mp make_pair
#define nod first
#define cost second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

long long D[250005],itnod[250005],n,m,x,y,c;
bool Used[250005];

vector < pair <int, int>> G[250005];
queue < int > Q;

int main()
{
    f>>n>>m;
    vector< pair <int,int>>::iterator vecin;
    for(int i=1; i<=m; i++)
        f>>x>>y>>c,G[x].pb(mp(y,c));
    for(int i=1; i<=n; i++)
    {
        D[i]=inf;
        Used[i]=false;
        itnod[i]=0;
    }
    D[1]=0;
    Q.push(1);
    while(!Q.empty())
    {
        int Nod=Q.front();
        Q.pop();
        Used[Nod]=false;
        for(vecin=G[Nod].begin(); vecin!=G[Nod].end(); vecin++)
            if(D[(*vecin).nod]>D[Nod]+(*vecin).cost)
            {
                D[(*vecin).nod]=D[Nod]+(*vecin).cost;
                if(!Used[(*vecin).nod])
                {
                    Used[(*vecin).nod]=true;
                    Q.push((*vecin).nod);
                    if(++itnod[(*vecin).nod]>n)
                    {
                        g<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
    }
    for(int i=2; i<=n; i++)
        g<<D[i]<<" ";

    return 0;
}