//Dijkstra cu heap si citire parsata
#include <cstdio>
#include <cstring>
#define N 50001
#define S_MAX 65536
#define inf 0x3f3f3f3f

struct adr
{
    int val,cost;
    adr *urm;
} *L[N];

int A[N],D[N],P[N];
char S[S_MAX];
int k;

void down(int tata, int n)
{
    int fiu=tata<<1,nod=A[tata];
    if (fiu<n && D[A[fiu+1]]<D[A[fiu]]) fiu++;
    while (fiu<=n && D[nod]>D[A[fiu]])
    {
        A[tata]=A[fiu];
        P[A[fiu]]=tata;
        tata=fiu; fiu<<=1;
        if (fiu<n && D[A[fiu+1]]<D[A[fiu]]) fiu++;
    }
    A[tata]=nod;
    P[nod]=tata;
}

void up(int fiu)
{
    int nod=A[fiu],tata=fiu>>1;
    while (fiu && D[nod]<D[A[tata]])
    {
        A[fiu]=A[tata];
        P[A[tata]]=fiu;
        fiu=tata; tata>>=1;
    }
    A[fiu]=nod;
    P[nod]=fiu;
}

void read(int &nr)
{
    nr=0;
    for (; S[k]<'0' || S[k]>'9'; k++)
        if (k==S_MAX-1)
        {
            fread(S,1,S_MAX,stdin);
            k=-1;
        }

    for (; S[k]>='0' && S[k]<='9'; k++)
    {
        nr=10*nr+S[k]-'0';
        if (k==S_MAX-1)
        {
            fread(S,1,S_MAX,stdin);
            k=-1;
        }
    }
}

int main()
{
    int n,m,i,j,x,y,z,dmin,nod;
    adr *p;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	fread(S,1,S_MAX,stdin);
	read(n); read(m);
	for (i=1; i<=m; i++)
	{
	    read(x); read(y); read(z);
	    p=new adr;
	    p->val=y; p->urm=L[x]; p->cost=z;
	    L[x]=p;
	}
	for (i=1; i<=n; i++) A[i]=i, P[i]=i;
    memset(D,inf,sizeof(D));
    for (p=L[1]; p; p=p->urm) D[p->val]=p->cost;

    for (i=n>>1; i; i--) down(i,n);
    int cn=n;
    for (i=1; i<n; i++)
    {
        dmin=D[A[1]];
        nod=A[1];

        for (p=L[nod]; p; p=p->urm)
            if (dmin+p->cost<D[p->val])
            {
                D[p->val]=dmin+p->cost;
                up(P[p->val]);
            }
        A[1]=A[cn--];
        down(1,cn);
    }

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

    return 0;
}