#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";

#define MAXN  50005
#define Min(a, b)  ((a) < (b) ? (a) : (b))

vector <pair <int, int> > adj[MAXN];     int n;

void read_in(void)
{
    ifstream in(iname);
    int cnt_edges, x, y, cst;

    in >> n >> cnt_edges;
    for (; cnt_edges > 0; -- cnt_edges)
        in >> x >> y >> cst,
        adj[x].push_back( make_pair(y, cst) );
    in.close();
}

vector <int> BF(void)
{
    const int infinity = int(1e9);
    deque <int> que;
    vector <int> dist(n + 1, infinity), inq(n + 1, 0);

    dist[1] = 0, que.push_back(1), inq[1] = 1;
    for (; que.size(); que.pop_front()) {
        int x = que.front();
        for (int i = 0; i < (int)adj[x].size(); ++ i) {
            int y = adj[x][i].first, cst = adj[x][i].second;
            if (dist[y] > dist[x] + cst) {
                dist[y] = dist[x] + cst;
                if (!inq[y])
                    que.push_back(y), inq[y] = 1;
            }
        }
        inq[x] = 0;
    }
    for (int i = 1; i <= n; ++ i) if (dist[i] == infinity)
        dist[i] = 0;
    return dist;
}

int main()
{
    read_in();
    vector <int> dist(BF());
    ofstream out(oname);
    for (int i = 2; i <= n; ++ i)
        out << dist[i] << " ";
    out.close();

    return 0;
}