#include <cstdio>
#include <queue>
#include <vector>

using namespace std;
const int NMAX = 50004;
const int inf = 1000000;
vector <pair<int,int> > graf[NMAX];
queue <int> coada;
int vizitat[NMAX],costuri[NMAX];
int n,m;

void afisare()
{
    for(int i = 2; i <= n ; i++)
        printf("%d ",costuri[i]);
}


void bellmanford(int start)
{
    int nod ,vecin,cost;
    coada.push(start);
    while(!coada.empty())
    {
        nod = coada.front();
        coada.pop();
        for(vector <pair<int,int> >:: iterator it = graf[nod].begin() ; it != graf[nod].end() ; it++)
        {
                vecin = it->first;
                cost = it->second;
            if(costuri[vecin] > costuri[nod] + cost)
            {
                costuri[vecin] = costuri[nod]+cost;
                vizitat[vecin]++;
                if(vizitat[vecin] > n)
                {
                    printf("Ciclu negativ!");
                    return;
                }
                coada.push(vecin);
            }
        }
    }
    afisare();
}

void preparation()
{
    for(int i = 1 ; i <= n ; i++)
        costuri[i] = inf;
    costuri[1] = 0;
}

void read()
{
    int x,y,cost;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i = 0 ; i< m ; i++)
    {
        scanf("%d %d %d",&x,&y,&cost);
        graf[x].push_back(make_pair(y,cost));
    }
}


int main()
{
    read();
    preparation();
    bellmanford(1);
    return 0;
}