#include <fstream>
#include <set>
#include <queue>

using namespace::std;

int n, m;
vector<vector<pair<int, int> > > g;
priority_queue<pair<int, int> > pq;

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

    fin >> n >> m;

    g.resize(n + 1);    
    while(m--) {
        int a, b,c;
        fin >> a >> b >>c;
        g[a].push_back(pair<int, int>(b, c));
    }

    vector<int> bestDist(n + 1, 1000000000);
    bestDist[1] = 0;

    pq.push(pair<int, int>(0, 1));
    while(pq.size()) {
        pair<int, int> p = pq.top();
        pq.pop();
        int currNode = p.second;
        int currDist = -p.first;

        for(pair<int, int> &edge: g[currNode]) {
            if (currDist + edge.second < bestDist[edge.first]) {
                bestDist[edge.first] = currDist + edge.second;                
                pq.push(pair<int, int>(-bestDist[edge.first], edge.first));
            }
        }
    }

    for(int i = 2; i <= n; i++) {
        fout << (bestDist[i] == 1000000000 ? 0 : bestDist[i]) << ' ';
    }
}