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

using namespace std;

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

void djikistra(int startNode, int n, vector<vector<pair<int,int>>> graph) {

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
    Q.push({0, startNode});
    vector<int> distances(n+1, 1e9);
    distances[startNode] = 0;

    while(!Q.empty()) {
        int currentNode = Q.top().second;
        Q.pop();

        for(auto ngh : graph[currentNode]) {
            if(distances[ngh.second] > distances[currentNode] + ngh.first) {
                distances[ngh.second] = distances[currentNode] + ngh.first;
                Q.push({distances[ngh.second], ngh.second});
            }
        }
    }

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

}

int main() {

    

    int n,m;
    fin >> n >> m;

    vector<vector<pair<int,int>>> graph(n+1, vector<pair<int,int>>());

    for(int i=1; i<=m; i++) {
        int nod1, nod2, dist;
        fin >> nod1 >> nod2 >> dist;

        graph[nod1].push_back({dist, nod2});
    }

    djikistra(1, n, graph);

    return 0;
}