#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();

     if(viz[k])
         continue;

     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++)
        if(distanta[i] < 999999)
            g << distanta[i] << " ";
        else g << 0 << " ";

}