#include <bits/stdc++.h>
using namespace std;
  
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int NMax = 5e4 + 5;
const int inf = 1e9;

vector< vector< pair< int, int > > > G(NMax);
vector< int > dist(NMax, inf);

void dijkstra(int nodStart) {
    set< pair< int, int > > q;
    dist[nodStart] = 0;
    q.insert(make_pair(dist[nodStart], nodStart));

    while(!q.empty()) {
        int tempNode = q.begin()->second; q.erase(q.begin());

        for(auto vecin: G[tempNode]) {
            int len = vecin.second;

            if(dist[tempNode] + len < dist[vecin.first]) {
                q.erase(make_pair(dist[vecin.first], vecin.first));
                dist[vecin.first] = dist[tempNode] + len;
                q.insert(make_pair(dist[vecin.first], vecin.first));
            }
        }
    }
}

int main() {
 
    int n, m; in >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int x, y, c; in >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }

    dijkstra(1);

    for(int i = 2; i <= n; ++i) {
        out << dist[i] << " ";
    }
    
    in.close(); out.close();
  
    return 0;
}