#include<cstdio>
#define N 50001
#define INF 666666666

struct nod
{
long nd;
long cost;
nod *next;
};

nod *xx[N];
long n,m,k;
long d[N],h[N],poz[N];

void add(long x,long y,long z)
{
nod *q;
q=new(nod);
q->nd=y;
q->cost=z;
q->next=xx[x];
xx[x]=q;
}

void rd()
{
scanf("%ld%ld",&n,&m);
long x,y,z;
for(long i=1;i<=m;i++)
    {
    scanf("%ld%ld%ld",&x,&y,&z);
    add(x,y,z);
    add(y,x,z);
    }
}

void sch(long a,long b)
{
long t=h[a];h[a]=h[b];h[b]=t;
t=poz[h[a]];poz[h[a]]=poz[h[b]];poz[h[b]]=t;
}

void Hup(int x)
{
while(x/2&&d[h[x]]<d[h[x/2]])
    sch(x,x/2),x/=2;
}

void Hadd(int x)
{
h[++k]=x;
Hup(k);
}

void Hdown(int x)
{
int u=x;
while(1)
    {
    if(x*2<=k&&d[h[x]]>d[h[x*2]]) u=x*2;
    if(x*2<k&&d[h[u]]>d[h[x*2+1]]) u=x*2+1;
    if(x==u) break;
    sch(u,x);
    x=u;
    }
}

void Hdel(int x)
{
sch(k,x);
k--;
Hdown(x);
}

void dijkstra()
{
long i;
for(i=1;i<=n;i++)
    d[i]=INF,poz[i]=-1;
Hadd(1);
d[1]=0;
while(k)
    {
    long u=h[1];
    Hdel(1);
    poz[u]=-1;
    for(nod *q=xx[u];q->nd;q=q->next)
        if(d[q->nd]>d[u]+q->cost)
            {
            d[q->nd]=d[u]+q->cost;
            if(poz[q->nd]!=-1)
                Hup(poz[q->nd]);
            else
                Hadd(q->nd);
            }
    }
}

void af()
{
for(long i=2;i<=n;i++)
    printf("%ld ",d[i]);
}
    
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);

rd();
dijkstra();
af();

return 0;
}