//#include <cstdio>
#include <cstring>
#include <fstream>

const int vv=50005;
const int 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);
    ifstream fin("dijkstra.in");
    //scanf("%d%d", &n, &m);
    fin>>n>>m;
    int z,x,c;
    /*for (int i=1; i<=n; i++)
    {
     //   w[i]=NULL;
        //a[i]=i;
    }*/
    nod *p;
    int o=0;
    if (m<n)
        o=1;
    for (int i=1; i<=m; i++)
    {
        //scanf("%d%d%d", &z, &x, &c);
        fin>>z>>x>>c;
        p=new nod;
        p->val=x;
        p->cost=c;
        p->next=w[z];
        w[z]=p;
        if (i<=n)
            a[i]=i;
    }
    //fclose(stdin);
    fin.close();
}

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--]=aux;
    }
		construire(m);
		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);
    ofstream fout("dijkstra.out");
    for (int i=2; i<=n; i++)
        if (d[i]!=inf)
            //printf("%d ", d[i]);
            fout<<d[i]<<" ";
        else
            //printf("0 ");
            fout<<0<<" ";
    fclose(stdout);
}

int main()
{
    citire();
    m=n;
    dijkstra();
    afisare();
    return 0;
}