//GRAF ORIENTAT PONDERAT
#include <iostream>
#include <fstream>
#define INF 25004
#define NMAX 50004
#define MMAX 250004
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n; //nr noduri
int m; //nr muchii
struct graf{ //structura listei de adiacenta (alocare dinamica)
    int nod;
    int cost;
    struct graf *urm;
}*L[NMAX],*p;

int d[NMAX]; //distanta de la sursa la fiecare nod
int viz[NMAX]; //noduri vizitate (epuizate/explorate complet)

void citire()
{
    int a,b,c;
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>a>>b>>c;
        //muchie a->b de cost c
        p=new graf;
        p->nod=b;
        p->cost=c;
        p->urm=L[a];
        L[a]=p;
    }
}

void afisD()
{
    for(int i=2;i<=n;++i)
    {
        if(d[i]==INF)
            out<<"0 ";
        else
            out<<d[i]<<" ";
    }
    out<<"\n";
}

void dijkstra(int source)
{
//initializeaza distantele cu INF
    for(int i=1;i<=n;++i)
        d[i]=INF;
    d[source]=0; //distanta sursa->sursa = 0

//repeta de n ori (pana cand epuizam nodurile)
    bool ok=true;
    while(ok==true)
    {
        ok=false;

        //extrage nodul nevizitat de distanta minima
        int mn=INF,act;

        for(int i=1;i<=n;++i)
            if(viz[i]==false && mn>d[i])
                mn=d[i], act=i, ok=true;

        viz[act]=true;

        //exploreaza vecinii nodului extras SI actualizeaza distanta sursa->actual->vecin
        for(graf *p=L[act];p!=NULL;p=p->urm)
        {
            int vecin=p->nod;
            int cost=p->cost;

            if(d[vecin] > d[act]+cost)
                d[vecin] = d[act]+cost;
        }
    }
}

int main()
{
    citire();

    int source=1;
    dijkstra(source);

    afisD();

    return 0;
}