#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <set>
#define N 50005
#define cost first
#define node second
#define INF 100000005
#define mp make_pair
using namespace std;
ifstream in ("dijkstra.in");
ofstream out("dijkstra.out");

vector<pair<int,int> > g[N];
bitset<N> v;
set<pair<int,int> > s;
int n, m;
long long d[N];

void dijkstra() {
        for (int i = 1; i <= n; i++)
                d[i] = INF;
        d[1] = 0;
        int mn, crnode;
        s.insert(mp(0, 1));
        while (s.size() > 0) {
                crnode = s.begin() -> node;
                s.erase(s.begin());
                v[crnode] = 1;
                for (int j = 0; j < g[crnode].size(); j++) {
                        if (!v[g[crnode][j].node] && d[g[crnode][j].node] > d[crnode] + g[crnode][j].cost) {
                                if (d[g[crnode][j].node] != INF)
                                        s.erase(s.find(mp(d[g[crnode][j].node], g[crnode][j].node)));
                                d[g[crnode][j].node] = d[crnode] + g[crnode][j].cost;
                                s.insert(mp(d[g[crnode][j].node], g[crnode][j].node));
                        }
                }
        }
}

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

        int x, y, z;
        for (int i = 1; i <= m; i++) { in >> x >> y >> z;
                g[x].push_back(mp(z, y));
        }
        dijkstra();

        for (int i = 2; i <= n; i++) {
                out << (d[i] != INF ? d[i] : 0) << " ";
        }
        return 0;
}