#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int NMAX = 50005;
const int INF = 0x3f3f3f3f;

int n, m, x, y, wt, dist[NMAX];
vector<vector<pair<int,int>>> graf(NMAX);

void citire()
{
    f>>n>>m;
    for (int i=1; i<=m; i++)
    {
        f>>x>>y>>wt;
        graf[x].push_back({y, wt});
    }
}

void dijkstra(int start)
{
    for(int i=1;i<=n;i++)
        dist[i]=INF;
    set <pair<int,int>> s;
    s.insert({0, start});
    dist[start] = 0;
    while (!s.empty())
    {
        int from, crt;
        tie(crt, from) = *(s.begin());
        s.erase(s.begin());
        for (auto i : graf[from])
        {
            if (crt+i.second < dist[i.first])
                {
                    if (dist[i.first]!=INF)
                     s.erase({dist[i.first], i.first});
                    dist[i.first] = crt+i.second;
                    s.insert({dist[i.first], i.first});
                }
        }
    }

}

void rezolvare()
{
    dijkstra(1);
    for (int i=2; i<=n; i++)
        if(dist[i] == INF)
         g<<0<<' ';
         else
         g<<dist[i]<<' ';

}

int main()
{
    citire();
    rezolvare();
    return 0;
}