#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 BASIC_READ_WRITE */
#define nl '\n'
#define sp ' '
#if __cplusplus >= 201703L
template <istream& is = cin, typename... T>
istream& read(T&... args) {
    (is >> ... >> args);
    return is;
}

template <ostream& os = cout, typename... T>
ostream& write(const T&... args) {
    (os << ... << args);
    return os;
}
#else
// Read this (it explains everything; I really recommend): https://kevinushey.github.io/blog/2016/01/27/introduction-to-c++-variadic-templates/
template <ostream& os = cout, typename T>
ostream& write(const T& args) {
    os << args;
    return os;
}

template <ostream& os = cout, typename T, typename... Rest>
ostream& write(const T& args, const Rest&... rest) {
    write<os>(args);
    write<os>(rest...);
    return os;
}

template <istream& is = cin, typename T>
istream& read(T& args) {
    is >> args;
    return is;
}

template <istream& is = cin, typename T, typename... Rest>
istream& read(T& args, Rest&... rest) {
    read<is>(args);
    read<is>(rest...);
    return is;
}
#endif
/* #endregion READ_WRITE */
/* #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 READ_WRITE */
template <istream& is = cin, typename T>
istream& readVector(vector<T>& v, szt start, szt end) {
    loopf(i, start, end)
        read<is>(v[i]);
    return is;
}
template <istream& is = cin, typename T>
istream& readMatrix(matrix<T>& v, szt starti, szt endi, szt startj, szt endj) {
    loopf(i, starti, endi)
        loopf(j, startj, endj)
            read<is>(v[i][j]);
    return is;
}
template <ostream& os = cout, typename T>
ostream& writeVector(vector<T>& v, szt start, szt end) {
    loopf(i, start, end)
        write<os>(v[i], sp);
    write<os>(nl);
    return os;
}
template <ostream& os = cout, typename T>
ostream& writeMatrix(matrix<T>& v, szt starti, szt endi, szt startj, szt endj) {
    loopf(i, starti, endi) {
        loopf(j, startj, endj)
            write<os>(v[i][j], sp);
        write<os>(nl);
    }
    return os;
}
/* #endregion READ_WRITE */
/* #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;
};
matrix<nod> graf;

void solve() {
    i32 n, m;
    f >> n >> m;
    graf = createMatrix<nod>(n + 1, 0);
    loopf(_, 1, m) {
        i32 a, b, c;
        f >> a >> b >> c;
        graf[a].push_back(nod(b, c));
    }

    // first: distanta pana la second
    // second: nodId
    priority_queue<pair<i32, i32>, vector<pair<i32, i32>>, greater<pair<i32, i32>>> Q;
    vector<i32> distance(n + 1, INT_MAX);
    set<i32> s;
    distance[1] = 0;
    Q.push({ 0, 1 });
    while (!Q.empty()) {
        auto a = Q.top();
        s.insert(a.second);
        for (auto&& child : graf[a.second]) {
            if (!s.count(child.id)) {
                distance[child.id] = min(distance[child.id], distance[a.second] + child.greutate);
                Q.push({ distance[child.id], child.id });
            }
        }
        Q.pop();
    }

    loopf(i, 2, n) g << distance[i] << sp;
}

int main() {
    FIO;
    i32 t = 1;
    while (t--)
        solve();
}