//#include <stdio.h>
#include <vector>
#include <queue>
#include <fstream>
#include <ctime>

clock_t end;
clock_t start;

 
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
 
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);
    fin >> n >> m;
    for (int i=0;i<n;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);
        fin >> sursa >> dest >> cost;

        muchie_0.dest=dest;
        muchie_0.cost=cost;
 
        noduri[sursa].vecini.push_back(muchie_0);
    }
    
    start = clock();

    noduri[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(noduri[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[noduri[crt].vecini[i].dest].cost = noduri[crt].cost+noduri[crt].vecini[i].cost;
                myQueue.push(noduri[crt].vecini[i].dest);
            }
        }
    }
    
    end = clock();



    for(int i=2; i<=n; i++)
    {
        //printf("%d ", noduri[i].cost);
        fout << noduri[i].cost << " ";
    }
    fout<<"\n";
    //printf("\n");
    //printf("Duratie: %.2fs\n", (double)(end - start)/CLOCKS_PER_SEC);
 
    return 0;
}