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);
    while(m--)
    {
	scanf("%d %d %d\n", &p, &q, &c);
	t=new nod;
	t->x=q;
	t->c=c;
	t->n=a[p];
	a[p]=t;
	
    }
}

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

    while(!Q.empty())
    {
	u=Q.top();
	Q.pop();


	for(it=a[u]; it ;it=it->n)
	    if(d[u]+it->c < d[it->x])
	    {
		d[it->x]=d[u]+it->c;
		 Q.push(it->x);
		
	    }
    }

    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();
    dijkstra();
    return 0;
}