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

using namespace std;

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

int n,m;
vector<vector<pair<int,int>>> graph(50005, vector<pair<int,int>>());

void djikistra(int startNode) {

    priority_queue<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() {

    

    
    fin >> n >> m;

    

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

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

    djikistra(1);

    return 0;
}