#include<fstream>
#include<vector>
#include<queue>
#define INF 1000000000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
class compare
{
    public:
    int operator() (const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second>p2.second;
    }
};
int dist[50002];  
int main()
{
    int n,v1,v2,cost,m,cv,v,l;
    in>>n>>m;
    vector<pair<int, int> > graph[n+1];
    priority_queue<pair<int, int>, vector<pair<int, int> >, compare> q; 
    for(int i=1; i<=m; i++)
    {
        in>>v1>>v2>>cost;
        graph[v1].push_back(pair<int, int> (v2, cost));
    }
    for(int i=2; i<=n; i++)dist[i] = INF;
    q.push(pair<int, int>(1, dist[1]));
    while(!q.empty())
    {
        cv=q.top().first;
        q.pop();
		l=graph[cv].size();
        for(int i=0;i<l;i++)
        {
            v=graph[cv][i].first;
            cost=graph[cv][i].second;
            if(dist[v]>dist[cv]+cost)
            {
                dist[v]=dist[cv]+cost;
                q.push(pair<int, int>(v, dist[v]));
            }
        }
    }
    for(int i=2;i<=n;i++)if(dist[i]<INF)out<<dist[i]<<" ";else out<<0<<" ";
}