#include<iostream>
#include<vector>
#include<list>
#include<queue>
#include<fstream>
# define INF 0x3f3f3f3f
using namespace std;

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

list<pair<int,int>> graf[50005];
int n, m;
int inpq[50005];


void Read()
{
    int i, x, y, z;

    f >> n >> m;
    for(i = 1; i <= m; i++)
    {
        f >> x >> y >> z;
        graf[x].push_back(make_pair(y, z));
    }
    f.close();

}


void Dijkstra(int src)
{
     priority_queue< pair<int,int>, vector <pair<int,int>> , greater<pair<int,int>> > pq;
     //vector<int> distance(n + 1, 10000);
     int distance[50005];

     for(int i= 0; i <= n+1; i++)
        distance[i] = INF;

     pq.push(make_pair(0,src));
     inpq[src] = 1;
     distance[src] = 0;

     while(!pq.empty())
     {
         int nod = pq.top().second;
         pq.pop();
         inpq[nod] = 0;

         list< pair<int, int> >::iterator it;

         for(it = graf[nod].begin(); it != graf[nod].end(); ++it)
         {
             int x = (*it).first;
             int weight = (*it).second;

             if(distance[x] > distance[nod] + weight)
             {
                 distance[x] = distance[nod] + weight;
                 if(inpq[x] == 0)
                 {
                    pq.push(make_pair(distance[x], x));
                    inpq[x] = 1;
                 }
             }
         }
     }

     for(int i = 2; i <= n; i++)
        if(distance[i] != INF)
            g << distance[i] << " ";
        else
            g << 0 << " ";

}

int main()
{
    Read();
    Dijkstra(1);

    g.close();
    return 0;
}