#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
#define dim_maxi 50001
#define maxi 9999999


using namespace std;

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

priority_queue<pair <int, int> > Q;
vector<pair<int, int>> a[50001];
vector<int> viz(50001);
vector<int> distanta(dim_maxi, maxi);
int n, m;
pair<int, int> poz;
int k;

int main()
{

    int x, y, cost;
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {

        f >> x >> y >> cost;
        a[x].push_back(make_pair(y, cost));
    }


    Q.push(make_pair(0,1));

    distanta[1] = 0;

    while(!Q.empty())
    {
        k = Q.top().second;
        Q.pop();

        //daca nodul k e vizitat, merg  mai departen si intru in for
        if(viz[k])
            continue;

        //parcurg vectorul
        for(int i = 0; i < a[k].size(); i++)
        {
            poz = a[k][i];
            if(distanta[poz.first] > distanta[k] + poz.second)
                if(viz[poz.first] == 0)
                {
                    distanta[poz.first] = distanta[k] + poz.second;
                    //distanta[poz.first] = distanta[poz.first] * (-1);
                    Q.push(make_pair(-distanta[poz.first], poz.first));
                }
        }
        viz[k] = 1;
    }
    for(int i = 2; i <= n; i++)
        //daca exista lant direct, il afisez
        if(distanta[i] < 999999)
            g << distanta[i] << " ";
        else g << 0 << " ";

}