#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[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));
    }

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

        int index = p.second;
        if(viz[index] != 1)
        {
            viz[index] = 1;
            int lim = vecini[index].size();
            for(int k=0; k<lim; ++k)
            {
                int vecin = vecini[index][k];
                if(dist[vecin] > dist[index] + vecini_costuri[index][k])
                {
                    dist[vecin] = dist[index] + vecini_costuri[index][k];
                    heap.push(make_pair(-dist[vecin], vecin));
                }
            }
        }
    }

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

    return 0;
}