#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 50005;
const int inf = 1e9;
int N,M;
int dp[nmax];
bool viz[nmax];
vector < int > L[nmax];
vector < int > C[nmax];

struct str
{
    int nod, cost;
    bool operator < (const str &A) const
    {
        return cost > A.cost;
    }
};
priority_queue < str > Q;



inline void Read()
{
    int i,x,y,z;
    fin >> N >> M;
    for(i = 1; i <= M; i++)
    {
        fin >> x >> y >> z;
        L[x].push_back(y);
        C[x].push_back(z);
    }
}



inline void Dijkstra()
{
    for(int i = 2; i <= N; i++) dp[i] = inf;
    str w,w2;
    Q.push({1,0});
    while(!Q.empty())
    {
        w = Q.top(); Q.pop();
       // viz[w.nod] = true;
        for(unsigned int i = 0; i < L[w.nod].size(); i++)
        {
            int nnod = L[w.nod][i];
            int ncost = C[w.nod][i] + dp[w.nod];
            if(dp[nnod] > ncost)
            {
                dp[nnod] = ncost;
                Q.push({nnod,ncost});
            }
        }

    }
    for(int i = 2; i <= N; i++)
        fout << (dp[i] == inf? 0 : dp[i]) << " ";
}



int main()
{
    Read();
    Dijkstra();
    return 0;
}