#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct nod{
int n;
struct nod *u;
int c=60000000;
int *p;
};
struct nod h[60000];
struct nod *vecini[50001];
int n,noduri,muchii,d[50001],pozitii[50001];

inline int father(int nod){return nod/2;}
inline int left_son(int nod){return nod*2;}
inline int right_son(int nod){return nod*2+1;}
inline int minim(int a,int b){if(a>b)return a; return b;}
void sift(int k)
{
    int son=0;
    do{ if(left_son(k)<=n){ son=left_son(k);
                            if(right_son(k)<=n && h[right_son(k)].c < h[left_son(k)].c){ son = right_son(k); }
                            if( h[son].c >= h[k].c ){ son = 0; }

                          }
                          else son=0;

        if(son){struct nod aux=h[k];  h[k]=h[son]; *(h[k].p)=k; h[son]=aux; *(h[son].p)=son;
                k=son;
            }


      }while(son);
}

void percolate(int k)
{
struct nod vv=h[k];

while((k>1) && (vv.c < h[father(k)].c)){
                                        h[k]=h[father(k)];
                                        *(h[k].p)=k;
                                        k=father(k);
                                    }
h[k]=vv;
*(h[k].p)=k;
}

//eliminare nod poz k

void elim(int k)
{
    h[k]=h[n];
    n--;
    if((k>1) && (h[k].c < h[father(k)].c))percolate(k);
    else sift(k);

}

void actual(int k,int val)
{
    h[k].c=val;
    if((k>1) && (h[k].c < h[father(k)].c))percolate(k);
        else sift(k);

}



int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
int a,b,c;
scanf("%d %d",&noduri,&muchii);
int dim=sizeof(struct nod);



for(int i=1; i<=muchii; i++)
{
    scanf("%d %d %d",&a,&b,&c);
struct nod *au=(struct nod*)malloc(dim);
au->n=b;
au->c=c;
au->u=vecini[a];
vecini[a]=au;
}
//bagam toate nodurile in heap, cu distanta infinit
n=noduri;
for(int i=2; i<=noduri; i++){h[i].n=i; h[i].p=&pozitii[i]; *(h[i].p)=i; }
h[1].c=0;
h[1].p=&pozitii[1];
*(h[1].p)=1;

struct nod f;
while(n)
{
f=h[1];
d[f.n]=f.c;
elim(1);
for(struct nod *i=vecini[f.n]; i; i=i->u)
{
    actual(pozitii[i->n],minim(f.c + i->c,h[pozitii[i->n]].c));
}
}

for(int i=2; i<=noduri; i++)printf("%d ",d[i]);
    return 0;
}