#include<cstdio>
#include<vector>
#include<queue>
#define pii pair<int,int>
using namespace std;
const int nmax = 50005;
const int inf = (1<<31)-1;
int n,m,x,y,c,d[nmax],i;
vector<pii> v[nmax];
priority_queue<pii,vector<pii>,greater<pii> > q;
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
	    scanf("%d%d%d",&x,&y,&c);
	    v[x].push_back(make_pair(y,c));
	}
	d[1]=0; q.push(make_pair(0,1));
	for(i=2;i<=n;i++) d[i]=inf;
	while(!q.empty())
	{
	    x=q.top().second; q.pop();
	    for(vector<pii>::iterator it=v[x].begin();it!=v[x].end();it++)
            if(d[x]+it->second<d[it->first])
            {
                d[it->first]=d[x]+it->second;
                q.push(make_pair(d[it->first],it->first));
            }
	}
	for(i=2;i<=n;i++) (d[i]==inf)?(printf("0 ")):printf("%d ",d[i]);
	return 0;
}