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

using namespace std;

vector<vector<pair<int, int>>> arches;
vector<int> visited;
vector<int> distances;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // ordered queue, can be used heap also

void dijkstra(){
    pq.push({0, 1});
    distances[1] = 0;
    while(!pq.empty()){
        int node = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(!visited[node]){
            for(auto m : arches[node])
                if(m.second + cost < distances[m.first]){
                    distances[m.first] = m.second + cost;
                    pq.push({distances[m.first], m.first});
                }
            visited[node] = 1;
        }
    }
}

int main(){
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n, m, x, y, c;

    fin>>n>>m;
    arches.resize(n+1);
    visited.resize(n+1);
    for(int i=0;i<=n;i++)
        distances.push_back(2e9);
    for(int i=0;i<m;i++){
        fin>>x>>y>>c;
        arches[x].push_back({y, c});
    }

    dijkstra();

    for(int i=2;i<=n;i++){
        if(distances[i]!=2e9) fout<<distances[i]<<" ";
        else fout<<0<<" ";
    }

    return 0;
}