#include<fstream>
#include<vector>
#include<queue>
#define INF 10000000
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 main()
{
    int n, v1, v2, cost, m, cv, v;
    in>>n>>m;
    vector<pair<int, int> > graph[n+1];
    int dist[n+1];     
    priority_queue<pair<int, int>, vector<pair<int, int> >, compare> q;     // this acts as a heap
    for(int i=1; i<=m; i++)
    {
        in>>v1>>v2>>cost;
        graph[v1].push_back(pair<int, int> (v2, cost));
    }
    dist[1] = 0;
    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();
        for(int i=0;i<graph[cv].size();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++)out<<dist[i]<<" ";
}