#include <stdio.h>
#include <vector>
#include <queue>
 
using namespace std;
 
 
struct muchie
{
    int dest;
    int cost;
};
 
struct nod
{
    vector <muchie> vecini;
    int nrp;
    int cost;
};
 
nod noduri[50001];
queue <int> myQueue;

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for (int i=0;i<50001;i++){
        noduri[i].nrp=0;
        noduri[i].cost = 250000010;
    }
 
    //construim vectorul de adiacenta
    for(int i=1; i<=m; i++)
    {
        int sursa, dest, cost;
        muchie muchie_0;
 
        scanf("%d%d%d",&sursa,&dest,&cost);
 
        muchie_0.dest=dest;
        muchie_0.cost=cost;
 
        g[sursa].vecini.push_back(muchie_0);
    }
 
    g[1].cost=0;
    
    //nodul ce urmeaza sa fie inspectat
    myQueue.push(1);
 
    //parcurgem toate nodurile conectate la graful nostru
    while(!myQueue.empty())
    {
        int crt=myQueue.front();
        myQueue.pop();
 
        noduri[crt].nrp++;
        if(g[crt].nrp>m)
        {
            printf("Ciclu negativ!\n");
            return 0;
        }
        //Parcurgem toti vecinii
        for(unsigned int i=0; i<noduri[crt].vecini.size(); i++)
        {
            if(noduri[crt].cost+noduri[crt].vecini[i].cost < noduri[noduri[crt].vecini[i].dest].cost)
            {
                noduri[g[crt].vecini[i].dest].cost = noduri[crt].cost+noduri[crt].vecini[i].cost;
                myQueue.push(g[crt].vecini[i].dest);
            }
        }
    }
 
    for(int i=2; i<=n; i++)
        printf("%d ", g[i].cost);

    printf("\n");
 
    return 0;
}