#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int nMax = 50005;
const int INF = 2000000000;
bool viz[nMax];
int dp[nMax];
int n, m;

struct muchie
{
    int nod, cost;
    inline bool operator <(const muchie &A)const
    {
        return cost > A.cost;
    }
};
priority_queue <muchie> q;
vector <muchie> L[nMax];

inline void Read()
{
    int x;
    muchie w;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> w.nod >> w.cost;
        L[x].push_back(w);
    }
}

inline void Dijkstra()
{
    int i, nod;
    muchie w;
    for(i = 1; i <= n; i++)
        dp[i] = INF;
    w.nod = 1;
    w.cost = 0;
    dp[1] = 0;
    q.push(w);
    while(!q.empty())
    {
        w = q.top();
        q.pop();
        nod = w.nod;
        if(!viz[nod])
        {
            viz[nod] = true;
            for(auto it : L[nod])
            {
                if(dp[it.nod] > dp[nod] + it.cost)
                {
                    dp[it.nod] = dp[nod] + it.cost;
                    w.nod = it.nod;
                    w.cost = dp[it.nod];
                    q.push(w);
                }
            }
        }
    }
    for(i = 2; i <= n; i++)
        if(dp[i] == INF)    fout << "0 ";
        else fout << dp[i] << " ";
}

int main()
{
    Read();
    Dijkstra();
    fin.close();fout.close();
    return 0;
}