/*
Algoritm: Dijkstra cu heapuri

Complexitate: O( m * log(n) )

Observatii:
-Nodul de start a fost considerat nodul 1. Pentru a desemna alt nod de start sunt necesare cateva mici modificari;
-Prima pozitie a heapului este considerata 1. Astfel, tatal nodului i va fi i/2, fiul stanga i*2, iar fiul dreapta i*2+1;

*/
#include<stdio.h>
struct point
{
        int x,c;
        point *y;
}*g[50001],*q; /* Folosim listele pentru a evita gasirea nodurilor vecine in O(n)*/
int m,n,i,j,k,x,y,c,h[50001],d[50001],t[50001],p[50001],nod;
inline void intro(int x, int y, int c)
{
        point *q=new point;
        q->x=y;
        q->c=c;
        q->y=g[x];
        g[x]=q;
}
inline void swap(int i,int j)
{
        int x;
        x=h[i];
        h[i]=h[j];
        h[j]=x;
        x=p[h[i]];
        p[h[i]]=p[h[j]];
        p[h[j]]=x;
        /*Odata cu interschimbarea a doua elemente trebuie sa interschimbam si pozitiile lor in vectorul de pozitii*/
}
void heapup(int i)
{
        if(d[h[i/2]]<d[h[i]])return;
        swap(i,i/2);
        heapup(i/2);
}
void heapdown(int i)
{
        int st,dr;
        if(i*2>m) return;
        st=d[h[i*2]];
        if(i*2+1<=m)dr=d[h[i*2+1]];else dr=st+1;
        if(st<dr)
        {
                if(d[h[i]]<=st)return;
                swap(i,2*i);
                heapdown(i*2);
        }
        else
        {
                if(d[h[i]]<=dr)return;
                swap(i,2*i+1);
                heapdown(2*i+1);
        }
}
void scrie(int x)
{
        if(x!=1&&x!=0)scrie(t[x]);
        printf("%d ",x);
}
int main()
{
        freopen("dijkstra.in","r",stdin);
        freopen("dijkstra.out","w",stdout);
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
        {
                scanf("%d%d%d",&x,&y,&c);
                intro(x,y,c);
                intro(y,x,c);/* Aceasta instructiune va lipsi in cazul unui graf ordonat*/
        }
        for(i=1;i<=n;i++)
        {
                d[i]=2000000000; /*Initial toate distantele sunt considerate infinit*/
                h[i]=i;
                p[i]=i;
        }
        m=n;
        d[1]=0;/*Toate distantele mai putin cea a nodului initial, bineinteles*/
        d[0]=-1;/*Acest lucru este oarecum util pentru cazurile cand costul dintre doua norudi este nul si considerati 1 prima pozitie a heapului*/
        for(i=0;i<n;i++)
        {
                nod=h[1];/*Desemnam nodul pe care il expandam*/
                swap(1,m); /*Dupa ce am ales nodul pe care il expanda, (cel din varful heapupul) il mutam la coada*/
                m--; /* si scadem lungimea heapului, astfel incat algoritmul va lasa nodul curent in pace*/
                heapdown(1); /*Reordonam arborele*/
                for(q=g[nod];q!=NULL;q=q->y) /*Luam fiecare nod vecin cu cel pe care il expandam*/
                        if(d[q->x]>d[nod]+q->c) /*Verificam daca ajungem la el cu un cost mai bun*/
                        {
                                d[q->x]=d[nod]+q->c;/*Daca da, actualizam distanta, */
                                t[q->x]=nod;/* desemnam nodul curent ca fiind noul tata al nodului pe care l-am acutalizat*/
                                heapup(p[q->x]);/*si reordonam heapul*/
                        }
        }
        /*Scrierea*/
        for(i=2;i<=n;i++)
                if(d[i]==2000000000) printf("Nu se poate ajunge la nodul %d\n",i);/* Daca are costul infinit ( adica 2000000000, asa cum am initializat mai sus, inseamna ca nu s-a putut ajunge la nod*/
                else
                        {
                                //printf("Nodul: %d\nCostul: %d\nDrum: ",i,d[i]);
                                //scrie(t[i]);
                                //printf("%d\n\n",i);
                                printf("%d ",d[i]);
                        }
        return 0;
}