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

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

vector<pair<int,int>> graf[100];
int n, m;


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

}


void Djakstra(int src)
{
     priority_queue< pair<int,int>, vector <pair<int,int>> , greater<pair<int,int>> > pq;
     vector<int> distance(n + 1, 10000);

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

     while(!pq.empty())
     {
         int nod = pq.top().second;
         pq.pop();

         for(int i = 0; i < graf[nod].size(); i++)
         {
             int x = graf[nod][i].first;
             int weight = graf[nod][i].second;

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

     for(int i = 2; i <= n; i++)
        g << distance[i] << " ";

}

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

    return 0;
}