#include <bits/stdc++.h>

using namespace std;

ifstream ci ("dijkstra.in");
ofstream co ("dijkstra.out");

const int N=50005;
vector < pair<int,int> > a[N];
set < pair<int,int> > q;

int r[N], f[N], n, m, cost, x, y;

int main()
{
    ci >> n >> m;
    for (int i=1; i<=m; i++)
    {
        ci >> x >> y >> cost;
        a[x].push_back({y,cost});
    }
    for (int i=1; i<=n; i++)
    {
        r[i]=INT_MAX;
    }
    q.insert({0,1});
    r[1]=0;
    while (!q.empty())
    {
        int nod=q.begin()->second;
        f[nod]=1;
        q.erase(q.begin());
        for (auto muchie:a[nod])
        {
            int vecin=muchie.first, cost=muchie.second;
            if (r[vecin]>r[nod]+cost)
            {
                q.erase({r[vecin],vecin});
                r[vecin]=r[nod]+cost;
                q.insert({r[vecin],vecin});
            }
        }
    }
    for (int i=2; i<=n; i++)
    {
        if (r[i]==INT_MAX)
        {
            co << 0 << " ";
        }
        else
        {
            co << r[i] << " ";
        }
    }
    return 0;
}