#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;

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]) 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+1);
    visited.resize(n+1, false);
    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;
}