#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
/* #region TYPES */
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef size_t szt;
template <typename T>
using matrix = vector<vector<T>>;
/* #endregion TYPES */
/* #region LOOPS */
#define loopf(i, start, end) for (szt i = start; i <= (szt)end; i++)
#define loopb(i, end, start) for (szt i = end; i >= (szt)start; i--)
#define loopf_step(i, start, end, step) for (szt i = start; i <= (szt)end; i += step)
#define loopb_step(i, end, start, step) for (szt i = end; i >= (szt)start; i -= step)
/* #endregion LOOPS */
/* #region STL */
template <typename T>
matrix<T> createMatrix(szt n, szt m, T initVal = T()) {
    return matrix<T>(n, vector<T>(m, initVal));
}
/* #endregion STL */
/* #region UTILITY */
template <typename T>
bool inRange(const T& val, szt start, szt finish) {
    return start <= val and val <= finish;
}
#define ABS(x) ((x) < 0 ? !(x) : (x))
#define impar(x) (ABS(x) & 1)
#define par(x) (!(ABS(x) & 1))
#define FIO                            \
    ios_base ::sync_with_stdio(false); \
    cin.tie(nullptr);
/* #endregion UTILITY */
 
struct nod {
    i32 id = -1;
    i32 greutate = 0;
    nod(i32 i, i32 g)
        : id(i)
        , greutate(g) { }
    nod() = default;
};
i32 n, m, a, b, c, first_node, second_node, weight;
 
int main() {
    f >> n >> m;
    /// first: distanta pana la second
    /// second: nodId
    priority_queue<pair<i32, i32>, vector<pair<i32, i32>>, greater<pair<i32, i32>>> Q;
    unordered_map<i32, vector<nod>> graf(n + 1);
    vector<i32> d(n + 1, INT_MAX);
    vector<bool> procesed_nodes(n + 1);
 
    loopf(_, 1, m) {
        f >> a >> b >> c;
        graf[a].push_back(nod(b, c));
    }
 
    d[1] = 0;
    Q.push({ 0, 1 });
    while (!Q.empty()) {
        first_node = Q.top().second;
        Q.pop();
        procesed_nodes[first_node] = 1;
        for (auto it : graf[first_node]) {
            if (procesed_nodes[second_node])
                continue;
            second_node = it.id;
            weight = it.greutate;
            if (d[first_node] + weight < d[second_node]) {
                d[second_node] = d[first_node] + weight;
                Q.push({ d[second_node], second_node });
            }
        }
    }
 
    loopf(i, 2, n) g << (d[i] == INT_MAX ? 0 : d[i]) << ' ';
    f.close();
    g.close();
}