#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define INFI 0x3f3f3f3f

using namespace std;

typedef pair <int, int> pii;

bool vis[50001];
int n, m, sol[50001];
vector <pii> g[50001];
priority_queue <pii, vector <pii>, greater<pii> > h;

int main()
{
    int i,a,b,c,x,y;
    ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin>>n>>m;
	for (i=1;i<=m;++i)
	{
		fin>>a>>b>>c;
		g[a].push_back(make_pair(b,c));
	}
	memset(sol,0x3f,sizeof(sol));
	sol[1]=0;
	h.push(make_pair(1,0));
	while (!h.empty())
	{
	    x=h.top().first;
		y=h.top().second;
		h.pop();
		vis[x]=1;
		for (i=0;i!=g[x].size();++i)
			if (y+g[x][i].second<sol[g[x][i].first])
			{
				sol[g[x][i].first]=y+g[x][i].second;
				h.push(make_pair(g[x][i].first,sol[g[x][i].first]));
			}
        while (!h.empty()&&vis[h.top().first])
			h.pop();
	}
	for (i=2;i<=n;++i)
        if (sol[i]!=INFI)
            fout<<sol[i]<<" ";
        else
            fout<<"0 ";
	fout<<"\n";
	return 0;
}