#include <cstdio>
#include <algorithm>
#include <vector>
#define nods 50002
#define buffs 1048576
#define inf 2000000000
using namespace std;
FILE *f=freopen("dijkstra.in","r",stdin);
int n,m,pos=0,a,i,d[nods],viz[nods],mini;
char buff[buffs];
struct gigi
{
    int c,y;
} _x;
std::vector<gigi>v[nods],h;
inline bool cmp(gigi a,gigi b){ return(a.c>b.c);}
inline void read(int &x)
{
    while( buff[pos]<'0'||buff[pos]>'9') if(++pos==buffs) fread(buff,1,buffs,stdin),pos=0;
    x=0;
    while( buff[pos]>='0'&&buff[pos]<='9')
    {
        x=(x<<1)+(x<<3)+buff[pos]-'0';
        if(++pos==buffs) fread(buff,1,buffs,stdin),pos=0;
    }
}
int main()
{
    fread(buff,1,buffs,stdin);
    freopen("dijkstra.out","w",stdout);
    read(n);
    read(m);
    for(i=1;i<=n;i++)
       d[i]=inf;
    for(i=1; i<=m; i++)
    {
        read(a),read(_x.y),read(_x.c);
        v[a].push_back(_x);
    }

a=v[1].size();
for(i=0; i<a; i++){
   d[v[1][i].y]=v[1][i].c;
   h.push_back(v[1][i]);
}
make_heap(h.begin(),h.end(),cmp);
viz[1]=true;
while(!h.empty())
{
    _x=h.front();
    pop_heap(h.begin(),h.end(),cmp);h.pop_back();
    a=v[_x.y].size();
    viz[_x.y]=true;
    for(i=0;i<a;i++)
       if(!viz[v[_x.y][i].y]&&d[v[_x.y][i].y]>d[_x.y]+v[_x.y][i].c)
       {
           d[v[_x.y][i].y]=d[_x.y]+v[_x.y][i].c;
         //  v[_x.y][i].c=d[v[_x.y][i].y];
           h.push_back(d[v[_x.y][i].y]);//v[_x.y][i]
           push_heap(h.begin(),h.end(),cmp);
       }


}
for(i=2;i<=n;i++)
        if(d[i]==inf) printf("0 ");
    else
        printf("%d ",d[i]);
}