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

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

int n, m, start;


struct var{
    int nod, cost;
};

vector<var> G[NMAX];


void citire()
{
    int c,y;
    var x;
    var b;
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x.nod>>b.nod>>b.cost;
        x.cost = b.cost;
        G[x.nod].push_back(b);
        G[b.nod].push_back(x);
    }
}


int dist[NMAX];
void dijkstra(int start)
{
   priority_queue< pair<int, int>, vector<pair<int, int> >, greater< pair<int, int> > > pq;

   for(int i=1;i<=n;++i) dist[i] = INT_MAX;
   pq.push(make_pair(0, start));
   dist[start] = 0;

   while(!pq.empty())
   {
       int u = pq.top().second;
       pq.pop();
       for(int i=0;i<G[u].size();++i)
       {
           int v = G[u][i].nod;
           int cosst = G[u][i].cost;
           if(dist[u] + cosst < dist[v])
           {
               pq.push(make_pair(cosst, v));
               dist[v] = dist[u] + cosst;
           }
       }
   }
}

int main()
{
     citire();
     dijkstra(1);
     for(int i=1;i<=n;++i) g << dist[i] << " ";
    return 0;
}