using namespace std;
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#define maxn 50001
#define oo 0x3f3f3f3f
#define pb push_back
struct nod { int x, c;nod *n;};

nod *a[maxn];

int d[maxn],n;

struct cmp{
    bool operator()(const int &a, const int &b)const
    {
	if(d[a]>d[b]) return 1;
	return 0;
    }
};

void read()
{
    int m, p, q, c;
    nod *t;
    freopen("dijkstra.in","r",stdin);
    scanf("%d %d\n", &n, &m);
    
    char ax[32],*T;
    while(m--)
    {
	gets(ax);
	T=strtok(ax, " ");
	p=atoi(T);
	T=strtok(0, " ");
	q=atoi(T);
	T=strtok(0, "\n");
	c=atoi(T);

	//scanf("%d %d %d\n", &p, &q, &c);
	t=new nod;
	t->x=q;
	t->c=c;
	t->n=a[p];
	a[p]=t;
	//a[p].pb(nod(q, c));
    }
}

void bell()
{
   // priority_queue<int, vector<int>, cmp>Q;
    queue<int>Q;
    Q.push(1);
    bool use[maxn];
    memset(use, 0,sizeof(use));
    memset(d, oo, sizeof(d));
    d[1]=0;
    use[1]=1;
    int u;
   nod *it;

    int ok=1,nr;
    int i;
 /*   for(nr=1; nr<=n && ok ;++nr)
    {
	ok=0;
	for(i=1;i<=n;++i)
	    for(it=a[i]; it; it=it->n)
		if(d[i] + it->c < d[it->x])
		{
		    d[it->x]= d[i] + it->c;
		    ok=1;
		}
    }
*/


   while(!Q.empty())
    {
	u=Q.front();
	Q.pop();
//	use[u]=0;
	
	for(it=a[u]; it ;it=it->n)
	    if(d[u]+it->c < d[it->x])
	    {
		d[it->x]=d[u]+it->c;
		//if(!use[it->x])
		{
		    Q.push(it->x);
		  //  use[it->x]=1;
		}
	    }
    }

    
    for(i=1;i<=n;++i) if(d[i]==oo) d[i]=0;

    freopen("dijkstra.out","w",stdout);
    for(i=2;i<=n;++i)printf("%d ", d[i]);
    printf("\n");

}

int main()
{
    read();
    bell();
    return 0;
}