#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define inf 1000000

using namespace std;


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

vector <int> vecini[50005];
vector <int> vecini_costuri[50005];
priority_queue < pair<int, int> > heap;
int dist[50005];
int viz[50005];

int n, m;

int main()
{

    int x, y, c;
    fin>>n>>m;

    for(int i=1; i<=m; ++i)
    {
        fin >> x >> y >> c;
        vecini[x].push_back(y);
        vecini_costuri[x].push_back(c);
    }

    for(int i=1; i<=n; ++i)
    {
        if(i == 1)dist[i] = 0;
        else dist[i] = inf;
        heap.push(make_pair(-dist[i], i));
    }

//    cout << "vector dist: ";
//    for(int i = 1; i<=n; ++i)cout << dist[i] <<" ";
//    cout << '\n';

    while(!heap.empty())
    {
        pair<int , int> p;
        p = heap.top();
        heap.pop();

        //cout << "testam "<<p.second<<" "<<-p.first<<'\n';

        int nod = p.second;
        if(viz[nod] == 0)
        {
            viz[nod] = 1;
            int lim = vecini[nod].size();
           // cout << "avem de testat "<<lim<<" noduri\n";
            for(int k=0; k<lim; ++k)
            {
                int vec = vecini[nod][k];
                //cout << "testam "<<nod<<" "<<vec<<" "<<vecini_costuri[nod][k]<<'\n';
                if(dist[vec] > dist[nod] + vecini_costuri[nod][k])
                {
                    dist[vec] = dist[nod] + vecini_costuri[nod][k];
                    //cout<<"modif distanta pt "<<vec<<'\n';
                    heap.push(make_pair(-dist[vec], vec));
                }
            }
        }
    }

    for(int i=2; i<=n; ++i)
    {
        if(dist[i] == inf)
            dist[i] = 0;
        fout << dist[i] << " ";
    }

    return 0;
}