#include <iostream>
	#include <fstream>
	#include <vector>
	#include <queue>
	#define nmax 50001
	#define inf 1e9
	#define PII pair<int,int>

	using namespace std;

    ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	vector<PII> v[nmax];
	priority_queue<PII,vector<PII>,greater<PII> >h;
	int d[nmax], use[nmax], n, m;

	void dijkstra(int ns)
	{
	    int i, nod, vecin, cost;

	    for(i=1; i<=n; i++)d[i] = inf;
	    d[ns] = 0;
	    h.push({0,ns});

	    while(!h.empty())
	    {
	        nod = h.top().second;
	        h.pop();
	        use[nod] = 1;

	        for(i=0; i<v[nod].size(); i++)
            {
                vecin = v[nod][i].second;
                cost  = v[nod][i].first;
                if(!use[vecin] && d[nod] + cost < d[vecin])
	              {
	                 d[vecin] = d[nod] + cost;
	                 h.push({d[vecin],vecin});
                  }
            }
	    }
	}
	int main()
	{
	    int i, a, b, c;;

	    f>>n>>m;
	    for(i=1; i<=m; i++)
	    {
	        f>>a>>b>>c;
            v[a].push_back({c,b});
	    }

	    dijkstra(1);

        for(i=2;i<=n;i++)
           if(d[i]==inf) g<<0<<" ";
           else g<<d[i]<<" ";

	    return 0;
	}