#include <iostream>
#include <fstream>
using namespace std;

// ifstream fin("dijkstra.in");
// ofstream fout("dijkstra.out");

// #define cin fin
// #define cout fout

/**
    5 6
    1 2 1
    1 4 2
    4 3 4
    2 3 2
    4 5 3
    3 5 6
*/

const int nMax = 5000;

int nodes[nMax][nMax];
int dis[nMax];
bool visited[nMax];

int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    for (int i = 0; i < nMax; ++i) {
        dis[i] = 2e9;
        for (int j = 0; j < nMax; ++j) {
            nodes[i][j] = -1;
        }
    }
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        nodes[a - 1][b - 1] = c;
    }
    dis[0] = 0;
    visited[0] = true;
    for (int k = 0; k < n; ++k) {
        int smallIndex = 0;
        int mn = 2e9;
        for (int i = 0; i < n; ++i) {
            if (visited[i] == false && dis[i] < mn) {
                smallIndex = i;
                mn = dis[i];
            }
        }
        visited[smallIndex] = true;
        for (int i = 0; i < n; ++i) {
            if (nodes[smallIndex][i] != -1
                && visited[i] == false
                && dis[i] > dis[smallIndex] + nodes[smallIndex][i]) {
                dis[i] = dis[smallIndex] + nodes[smallIndex][i];
            }
        }
    }
    for (int i = 1; i < n; ++i) {
        cout << (dis[i] == 2e9 ? 0 : dis[i]) << " ";
    }
    return 0;
}