#include<cstdio>
#include<vector>
using namespace std;
#define NMAX 50005
#define INF 0x3f3f3f3f
vector < pair <int,int> > v[NMAX];
int n,m,x,y,c,cost,D[NMAX];
int aux,dH,p,H[NMAX],P[NMAX];
int main()
{
    int i;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=0;i<m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(make_pair(y,c));
    }
    for (i=2;i<=n;++i)
        D[i]=INF;
    H[1]=P[1]=1, dH=1;
    while (dH>0)
    {
        x=H[1];
        for (i=0;i<v[x].size();++i)
        {
            y=v[x][i].first, cost=v[x][i].second;
            if (D[y]>D[x]+cost)
            {
                D[y]=D[x]+cost;
                if (P[y])
                    c=P[y], p=c>>1;
                else
                    H[++dH]=y, c=P[y]=dH, p=c>>1;
                while (p>0)
                {
                    if (D[H[p]]>D[H[c]])
                    {
                        aux=H[p], H[p]=H[c], H[c]=aux;
                        P[H[p]]=p, P[H[c]]=c;
                        c=p, p=c>>1;
                    }
                    else
                        break;
                }
            }
        }
        aux=H[1], H[1]=H[dH], H[dH]=aux, --dH;
        P[H[1]]=1;
        p=1, c=p<<1;
        while (c<=dH)
        {
            if (D[H[c+1]]<D[H[c]] && c+1<=dH)
                ++c;
            if (D[H[p]]>D[H[c]])
                {
                    aux=H[p], H[p]=H[c], H[c]=aux;
                    P[H[p]]=p, P[H[c]]=c;
                    p=c, c=p<<1;
                }
                else
                    break;
        }
    }
    for (i=2;i<=n;++i)
        if (D[i]==INF) printf("0 ");
        else printf("%d ",D[i]);
    printf("\n");
    return 0;
}