#include <cstdio>
#include <cstring>
#define vv 50005
#define inf 0x3f3f3f3f

using namespace std;

struct nod
    {
        int val,cost;
        nod *next;
    };

nod *w[vv];
int n,m,q[vv],d[vv],a[vv];

void citire()
{
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d", &n, &m);
    int z,x,c;
    for (int i=1; i<=n; i++)
        w[i]=NULL;
    nod *p;
    for (int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &z, &x, &c);
        p=new nod;
        p->val=x;
        p->cost=c;
        p->next=w[z];
        w[z]=p;
    }
    fclose(stdin);
}

void construire(int n)
{
	int aux,q,w;
	for (int i=n/2; i>=1; i--)
	{
		w=i;
		q=0;
		while (q!=w && 2*w<=n)
		{
			q=w;
			if (2*w+1<=n && d[a[2*w]]>d[a[w*2+1]])
			{
				if (d[a[w]]>d[a[2*w+1]])
				{
					aux=a[w];
					a[w]=a[2*w+1];
					a[w*2+1]=aux;
					w=w*2+1;
				}
			}
			else
				if (d[a[w]]>d[a[2*w]])
				{
					aux=a[w];
					a[w]=a[2*w];
					a[w*2]=aux;
					w*=2;
				}
		}
	}
}

int extragere(int e)
{
	int aux;
    if (e!=0)
    {
		aux=a[1];
		a[1]=a[m--];
		a[m+1]=aux;
    }
		construire(m);
/*		if (q[a[1]]!=0)
		   extragere(e);*/
		return a[1];
}

void dijkstra()
{
//    for (int i=2; i<=n; i++)
//        d[i]=inf;
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    int k;
    for (int i=1; i<=n; i++)
    {
        if (i==1)
            k=extragere(0);
        else
            k=extragere(1);
        q[k]=1;
        if (d[k]==inf)
            return;
        for (nod *p=w[k]; p; p=p->next)
            if (d[k]+p->cost<d[p->val])
                d[p->val]=d[k]+p->cost;
    }
}

void afisare()
{
    freopen("dijkstra.out","w",stdout);
    for (int i=2; i<=n; i++)
        if (d[i]!=inf)
            printf("%d ", d[i]);
        else
            printf("0 ");
    fclose(stdout);
}

int main()
{
    citire();
    for (int i=1; i<=n; i++)
        a[i]=i;
    m=n;
    dijkstra();
    afisare();
    return 0;
}