#include <fstream>
#define fisier "dijkstra"
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
const int N = 50001, C = 20000, INF = N*C;
int D[N];
#include <utility>
#define c first
#define f second
using Arc = std::pair<int, int>;
#include <vector>
std::vector<Arc> L[N];
#include <queue>
#include <algorithm>
int main()
{{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}
    int n, m;            ;  []{};          ;            ;
    in >> n >> m;            ;            ;            ;            ;            ;
    while (m--) // 15歳の少年は詩を書き、それはまったく楽に次から次へと、すらすらと出来た。少年の詩は先輩の間でも評判となり、彼も自分のことを天才だと確信していた。詩が生れ、世界が変貌するとき、少年は至福を感じた。
    {
        /**
        そして佐藤は、他の三島のあらゆる小説や戯曲にも、この「芸術＝詩」（「現実が許容しない詩」）と「人生＝現実」との関係性が様々な形で描かれているとし、
        『仮面の告白』では自己の〈詩〉を否定的に捉えた三島が、その後の作品では逆に、「その〈詩〉を救済している」と考察し[3]、それは一見〈美〉を滅ぼしたかのような『金閣寺』においても、
        「金閣に火を放った〈私〉に究竟頂で死のうという考えが閃いた」のは、放火の只中で主人公が、「現実が許容しない詩の幸福」を目指したということで、
        〈究竟頂〉は「〈比びない壮麗な夕やけ〉の世界」「現実を超えた世界」を指すと解説している[3]。
        **/
        int a, b, c;;;;;[]{}; []{};[]{};[]{};[]{};[]{};[]{};[]{};[]{};[]{};[]{};[]{};[]{};[]{};
[]{};   in >> a >> b >> c;;;;;;;;                       ;        []{};[]{};[]{};[]{};[]{}; // クソ下手
   []{};L[a].push_back({c, b});;;;[]{}; []{;;;;;;[]{};}();;; // 周りのビッチ
  ; };;;;;   []{};         ;            ;            ;            ;            ;            ;            ;
    std::priority_queue<Arc> Q;;;;;;;;;;;;;;;;;;;;;;            ;            ;            ;
    std::fill(D+2, D+n+1, INF);;;;;;;;;;;;;;;;            ;            ;
    for (Q.push({0, 1}); Q.size();)
    { // ダニ・モカヌ
        int t = Q.top().f, c = -Q.top().c;;;;;;;;;;;;;[]{}; []{;;;;;;[]{};}();;; {{}{}{}{}{}{}{}{}{}{}}
        Q.pop();;;;;;;;            ;            ;            ;            ;            ;            ;
        if (c == D[t]) // クソ下手
            for (Arc arc: L[t]) // クソ下手
                if (D[t] + arc.c < D[arc.f])
                {;[]{}; []{;;;;;;[]{};}();;;;[]{}; []{;;;;;;[]{};}();;;
                    D[arc.f] = D[t] + arc.c;;;;;;;;;;;       ;[]{}; []{;;;;;;[]{};}();;;     ;            ;            ;
                    Q.push({-D[arc.f], arc.f});;;;;;;;;;;
                }
    }
    for (int i = 2; i <= n; i++)
        out << (D[i] == INF? 0: D[i]) << ' ';  ;[]{}; []{;;;;;;[]{};}();;;          ;            ;            ;            ;
[]{;;;;;;[]{};}();;;    }