#include <bits/stdc++.h>
#define Nmax 50005
#define INF 2000000000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct muchie
{
    int nod, cost;
    bool operator <(const muchie & A) const
    {
        return cost > A.cost;
    }
};

priority_queue <muchie> q;
vector <muchie> L[Nmax];
int dp[Nmax], viz[Nmax];
int n, m;

void Dijkstra()
{
    muchie w, w1;
    while(!q.empty())
    {
        w = q.top();
        q.pop();
        if(!viz[w.nod]);
        {
            viz[w.nod] = 1;
            for(auto it : L[w.nod])
                if(dp[it.nod] > dp[w.nod] + it.cost)
                {
                    dp[it.nod] = dp[w.nod] + it.cost;
                    w1.nod = it.nod;
                    w1.cost = dp[it.nod];
                    q.push(w1);
                }
        }
    }
}

int main()
{
    int i, x;
    muchie w;
    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> w.nod >> w.cost;
        L[x].push_back(w);
    }
    w.nod = 1;
    w.cost = 0;
    q.push(w);
    for(i = 1; i <= n; i++)
        dp[i] = INF;
    dp[1] = 0;
    Dijkstra();
    for(i = 2; i <= n; i++)
        if(dp[i] == INF) fout << "0 ";
        else    fout << dp[i] << " ";
    return 0;
}