#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 50005;
const int inf = 2000000000;
int N,M,dp[nmax];
bool viz[nmax];

struct el
{
    int nod,cost;
    bool operator < (const el &A) const
    {
        return cost > A.cost;
    }
};
vector < el > L[nmax];
priority_queue < el > Q;


inline void Read()
{
    int x,y;
    el w;
    fin >> N >> M;
    while(M--)
    {
        fin >> x >> y >> w.cost;
        w.nod = y; L[x].push_back(w);
    }
}

inline void Dijkstra()
{
    el w,w2;
    int nnod,nc;
    while(!Q.empty())
    {
        w = Q.top(); Q.pop();
        for(auto it : L[w.nod])
        {
            if(!viz[it.nod])
            {
                nc = w.cost + it.cost;
                if(nc < dp[it.nod])
                {
                    dp[it.nod] = nc; w2.cost = nc; w2.nod = it.nod;
                    viz[it.nod] = true;
                    Q.push(w2);
                }
            }
        }
    }
}


inline void Solve()
{
    for(int i = 2; i <= N; i++) dp[i] = inf;
    el w;
    w.nod = 1; w.cost = 0; Q.push(w);
    Dijkstra();
    for(int i = 2; i <= N; i++)
        fout << (dp[i] == inf? 0 : dp[i]) << " ";
    fout << "\n";
}


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