#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];
int n, m;

void Dijkstra()
{
    int i, j, c, len;
    muchie w, w1;
    while(!q.empty())
    {
        w = q.top();
        len = L[w.nod].size();
        q.pop();
        for(i = 0; i < len; i++)
        {
            j = L[w.nod][i].nod;
            c = L[w.nod][i].cost;
            if(dp[j] > dp[w.nod] + c)
            {
                dp[j] = dp[w.nod] + c;
                w1.nod = j;
                w1.cost = dp[j];
                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;
}