#include<fstream>
#include<iostream>
#include<vector>
#define MAXN 50001
#define INF 999999999

using namespace std;

int dist[MAXN];
int n, m;

struct vert {
    int x, y, c;
};

vector<vert> v;

void add(int x, int y, int c) {
    vert vertex;
    vertex.x = x;
    vertex.y = y;
    vertex.c = c;
    v.push_back(vertex);
}   

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

    in >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        in >> a >> b >> c;
        add(a, b, c);
    }

    for (int i = 0; i <= n; i++) {
        dist[i] = INF;
    }
    dist[1] = 0;

    short finished = 0;
    while (finished != 1) {
        finished = 1;
        for (auto i=v.begin();i!=v.end();i++) {
            int x = (*i).x;
            int y = (*i).y;
            int c = (*i).c;
            if (dist[y] > dist[x] + c) {
                dist[y] = dist[x] + c;
                finished = 0;
            }
        }
    }

    for (int i = 2; i<=n; i++) {
        if (dist[i] == INF) {
            out << "0 ";
        } else {
            out << dist[i] << " ";
        }
    }

    in.close();
    out.close();
    return 0;
}