#include <cstdio>
#include <vector>
#include <queue>
#define lim 60002

using namespace std;
int n, m , begin ,inf = 1<<30-1;
struct nod
{
    int v , c;/// Next , cost
}a;
vector <nod> graf[lim]; /// mi-am definit graful ca fiind
///un "vector" de tipul nod cu lungimea maxima definita mai sus de 60002
struct valori
{
    bool viz ; /// stim daca e vizitat (1 / 0)
    int dist;
}sir[lim];
struct comp{///struct de compare
    bool operator() (int a,int b)
    {
        return (sir[a].dist >= sir[b].dist);
    }
};
priority_queue <int, vector <int>, comp > Q;
///coada de prioritati
///cea care simuleaza heap-ul
void citire()
{
    scanf("%d %d",&n,&m);
    int unde ;
    for(int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d %d",&unde,&a.v,&a.c );///
        graf[unde].push_back(a);/// "pun"  nodul a in graf
    }
}
void initializare(int begin)
{
    sir[begin].viz = 1;
    sir[begin].dist = 0;
    for(int i = 2; i<=n ; ++i)
    {
        sir[i].dist = inf;
    }
}
void dijkstra()
{
    begin = 1;///nodul din care se pleaca
    initializare(begin);
    Q.push(begin);
    while(!Q.empty())///cat timp nu s-au terminat el din Queue(coada)
    {
        int min = Q.top(); /// iau minimul
        Q.pop();
        sir[min].viz= 1;
        for(int i=0;i<graf[min].size();i++)
        {
            if(!sir[graf[min][i].v].viz)///verificam daca minimul vecininului este nevizitat
            {
                int suma = sir[min].dist + graf[min][i].c;
                if(suma < sir[graf[min][i].v].dist)
                    sir[graf[min][i].v].dist= suma;///s-a modificat distanta(micsorandu-se)
                Q.push(graf[min][i].v);///bag in  coada vecinului min
            }
        }
    }

}
void in_final()///scrierea rezultatului
{
    for(int i=2; i <= n; ++i)
    {
        if(sir[i].dist == inf)
        {
            printf("0 ");
        }
        else
            printf("%d ",sir[i].dist);
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    in_final();
    return 0;
}