#include <stdio.h>
#include <vector>
#define inf 2147483647
using namespace std;


struct mc
{int a,c;
}nodcost;
vector<mc>v[50001];
int d[50001],p[50001],h[50001],nheap;


void swapy(int tata,int fiu)
{//fiu inseamna ala mai mare valoric, de mai jos
    int aux;
    aux=h[tata];
    h[tata]=h[fiu];
    h[fiu]=aux;
    p[h[tata]]=tata;
    p[h[fiu]]=fiu;
}

int sift()
{swapy(1,nheap);
nheap--;
int fiu,tata=1;
while(tata*2<=nheap)
{
    fiu=tata*2;
    if(fiu+1<=nheap&&d[h[fiu+1]]<d[h[fiu]])fiu++;
    if(d[h[tata]]>d[h[fiu]]){swapy(tata,fiu);tata=fiu;}
    else break;
}
return h[nheap+1];
}
void percolate(int fiu)
{
    int tata;
    while(fiu>1)
    {
        tata=fiu/2;
        if(d[h[tata]]>d[h[fiu]]){swapy(tata,fiu);fiu=tata;}
        else break;
    }
}



int main()
{freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
int n,m,i,j,a,b,mar,c;

scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
    scanf("%d%d%d",&a,&nodcost.a,&nodcost.c);
    v[a].push_back(nodcost);
}

for(i=0;i<=n;i++)
    {d[i]=inf;h[i]=p[i]=i;}
    d[1]=0;
    nheap=n;
    while(nheap>0)
    {
        a=sift();
        mar=v[a].size();
        for(i=0;i<mar;i++)
        {
            b=v[a][i].a;
            c=v[a][i].c;
            if(d[a]!=inf&&d[a]+c<d[b])
            {
                d[b]=d[a]+c;
                percolate(p[b]);
            }
        }
    }
    for(i=2;i<=n;i++)
        {if(d[i]==inf)printf("0");else printf("%d ",d[i]);}

    return 0;
}