#include <fstream>
#include <vector>
#include <climits>
#include <queue>
#define nmax 50005
#define inf INT_MAX

using namespace std;

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

int n, m, dist[nmax], h;
bool viz[nmax];
vector <pair <int, int> > vecini[nmax];
vector <pair <int, int> > ::iterator it;
priority_queue < pair<int, int>, vector < pair<int, int> >, greater < pair<int, int> > > pq;

void citire(){
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int  x, y, c;
        in >> x >> y >> c;
        vecini[x].push_back({y, c});
    }
}

void afisare(){
    for(int i = 2; i <= n; i++)
        if(dist[i] == inf)
          out << 0 << ' ';
        else
          out<<dist[i]<<' ';

}

void dijkstra(int plec){
    for(int i=1; i<=n; i++){
        dist[i]=inf;
        viz[i] = false;
    }
    dist[plec]=0;
    pq.push({dist[plec], plec});
    while(!pq.empty())
    {
        int minim = pq.top().second;
        pq.pop();
        if(!viz[minim])
        {
            viz[minim] = true;
            for(it = vecini[minim].begin(); it!=vecini[minim].end(); it++)
                if(dist[it->first] > dist[minim] + it->second)
                {
                    dist[it->first] = dist[minim] + it->second;
                    if(!viz[it->first])
                        pq.push({dist[it->first], it->first});
                }
        }
    }
}

int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}