#include <vector>
#include <fstream>
#include <iostream>
#include <queue>

using namespace std;

vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start)
{
    int n = graph.size();
    vector<int> dist(n, 1e9);
    
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
    
    pq.emplace(dist[start], start);
    
    while(!pq.empty())
    {
        pair<int, int> top = pq.top();
        int c = top.first;
        int node = top.second;
        pq.pop();
        
        if(c > dist[node]) continue;
        
        for(pair<int, int> p: graph[node])
        {
            int new_cost = c + p.second;
            
            if(new_cost < dist[p.first])
            {
                dist[p.first] = new_cost;
                pq.emplace(dist[p.first], p.first);
            }
            
        }
    }
    
    for(int i = 1; i <= n; i++) {
        if(dist[i] == 1e9) {
            dist[i] = 0;
        }
    }
    return dist;
}

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n, m;
    
    fin >> n >> m;
    
    vector<vector<pair<int, int>>> graph(n + 1);
    
    for(int i = 0; i < m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        graph[a].emplace_back(b, c);
    }
    
    vector<int> result = dijkstra(graph, 1);
    
    for(int i = 2; i <= n; i++) {
        fout << result[i] << ' ';
    }
    
    return 0;
}