#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=1000000000;
vector< pair<int,int> > G[50005];
int d[50005];
bool viz[50005];
int main()
{
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");
	int x,y,c,n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
    {
		cin>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
	}
    queue<int> Q;
    fill(d+2,d+n+1,INF);
	Q.push(1);viz[1]=true;
	while(!Q.empty())
    {
		int nod=Q.front();
		viz[nod]=false;
        for(auto u:G[nod])
			if(d[nod]+u.second<d[u.first])
            {
				d[u.first]=d[nod]+u.second;
				if(!viz[u.first])
					Q.push(u.first),
					viz[u.first]=true;
			}
	Q.pop();
    }
	for(int i=2;i<=n;i++)
		cout<<(d[i]<INF?d[i]:0)<<" ";
	return 0;
}