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

nod *a[maxn];

int d[maxn],n;
int poz;
char ax[DIM];
struct cmp{
    bool operator()(const int &a, const int &b)const
    {
	if(d[a]>d[b]) return 1;
	return 0;
    }
};

inline void cit(int &x)
{
	x=0;
	
	while(ax[poz]<'0' || ax[poz]>'9')
	{
		++poz;
		if(poz==DIM) fread(ax, 1, DIM, stdin), poz=0;
	}
	
	while(ax[poz]>='0' && ax[poz]<='9')
	{
		x=x*10+ax[poz]-'0';
		++poz;
		if(poz==DIM) fread(ax, 1, DIM, stdin), poz=0;
	}
}


void read()
{
    int m, p, q, c;
    nod *t;
    freopen("dijkstra.in","r",stdin);
	cit(n); cit(m);
	//scanf("%d %d\n", &n, &m);
    while(m--)
    {
		cit(p); cit(q); cit(c);
	//	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;

    while(!Q.empty())
    {
	u=Q.top();
	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;
		}
	    }
    }

    int i;
    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;
}