#include <fstream>
#include <vector>
#define inf 999999999
#define NMAX 50001
#define MMAX 250001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int nh,n,m,p,poz[NMAX],h[NMAX],d[NMAX];
struct NOD{int nod,cost;};
vector<NOD> a[MMAX];
vector<NOD>::iterator it;
void schimba(int i,int j){
    int aux=h[i];
    h[i]=h[j];
    h[j]=aux;
    poz[ h[i] ]=i;
    poz[ h[j] ]=j;
}
void heap_up(int k){
    int t,fiu;
    fiu=k;
    t=k/2;
    while(t)
    {
        if(d[ h[t] ]>d[ h[fiu] ])
          schimba(t,fiu);
        else
          break;
        fiu=t;
        t/=2;
    }
}
void heap_down(int k){
    int t,fiu;
    t=1;fiu=2;
    while(fiu<=k)
    {
        if(fiu+1<=k&&d[ h[fiu] ]>d[ h[fiu+1] ])
         ++fiu;
        if(d[ h[t] ]>d[ h[fiu] ])
          schimba(t,fiu);
        else
          break;
         t=fiu;
        fiu*=2;
    }
}
void citire(){
    NOD nd;
    f>>n>>m;
    p=1;
    int x,y,z;
    for(int i=1 ; i<=m ; ++i)
    {
        f>>x>>y>>z;
        nd.nod=y;
        nd.cost=z;
        a[x].push_back(nd);
        nd.nod=x;
        a[y].push_back(nd);
    }

    for(int i=1 ; i<=n ; ++i)
        d[i]=inf;
    d[p]=0;
    for(it=a[p].begin() ; it!=a[p].end() ; ++it)
        d[it->nod]=it->cost;

    for(int i=1 ; i<=n ; ++i)
        if(i!=p)
    {
        h[++nh]=i;
        poz[i]=nh;
        heap_up(nh);
    }
    else
        poz[i]=n+1;
}
int scot(){
    schimba(1,nh);
    --nh;
    heap_down(nh);
    return h[nh+1];
}
void dijkstra(){
    while(nh)
    {
        int k=scot();
        for(it=a[k].begin() ; it!=a[k].end() ; ++it)
            if(d[it->nod]>d[k]+it->cost)
        {
            d[it->nod]=d[k]+it->cost;
            heap_up(poz[it->nod]);
        }
    }
    for(int i=2 ; i<=n ; ++i)
        if(d[i]==inf)
          g<<0<<" ";
        else
          g<<d[i]<<" ";
        g<<'\n';
}
int main()
{
    citire();
    dijkstra();
    return 0;
}