#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
 
#define INF 1000000
 
using namespace std;
 
vector<pair<int, int> > *graf;
int n, m, *d;
 
ifstream in("dijkstra.in", ifstream::in);
ofstream out("dijkstra.out", ofstream::out);
 
void read_data()
{
    int x, y, cost;
     
    in >> n >> m;
    graf = new vector<pair<int, int> >[n];
     
    for (int i = 0; i < m; i++) {
        in >> x >> y >> cost;
        x--, y--;
        graf[x].push_back(make_pair(y, cost));
    }
}
 
void dijkstra(int s)
{
    int nod, dst, cost, v;
 
priority_queue<pair<int, int>, vector<pair <int, int> >, greater< pair<int, int> > > Q;
 
    d = new int[n];
     
    for (int i = 0; i < n; i++)
        d[i] = INF;
 
    d[s] = 0;
    Q.push(make_pair(d[s], s));
 
    while (!Q.empty()) {
        dst = Q.top().first;
        nod = Q.top().second;
         
        Q.pop();
 
        if (dst <= d[nod]) {
            for (unsigned int i = 0; i < graf[nod].size(); i++) {
                v = graf[nod][i].first;
                cost = graf[nod][i].second;
                if (d[v] > d[nod] + cost) {
                    d[v] = d[nod] + cost;
                    Q.push(make_pair(d[v], v));
                }
            }
        }
    }
}
 
 
int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    read_data();
    dijkstra(0);
 
    for (int i = 1; i < n; i++)
        out << (d[i] == INF ? 0:d[i]) << " ";
    out << endl;
    return 0;
}