#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50000;

int n, m;
int a, b, p;

vector < pair<int,int> > v[NMAX+1];
int distmin[NMAX+1];


void dist()
{
    priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > pq;
    for(int i=2; i<=n; i++)
        distmin[i] = INT_MAX;
    distmin[1] = 0;
    pq.push(make_pair(0,1));
    while(!pq.empty())
    {
        int nod = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(cost > distmin[nod])
            continue;
        for(auto a : v[nod])
        {
            int costfiu = cost+a.second;
            if(costfiu < distmin[a.first])
            {
                distmin[a.first] = costfiu;
                pq.push(make_pair(distmin[a.first],a.first));
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        fin >> a >> b >> p;
        v[a].push_back({b,p});
    }
    dist();
    for(int i=2; i<=n; i++)
        if(distmin[i] == INT_MAX)fout << 0 << ' ';
        else fout << distmin[i] << ' '; 
    return 0;
}