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

using namespace std;

vector<vector<pair<int, int>>> arches;
vector<bool> visited;
vector<int> distances;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

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

    int n, m, x, y, c;

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

    dijkstra();

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

    return 0;
}