#include <iostream>
#include<vector>
#include<fstream>
#include<utility>
#include<queue>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int infinit= 999999;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<int>  graf[50001];
vector<int> costuri[50001];
int dist_min[50001];
int n,m;

void dijkstra(int nod)
{queue<int> coada;
    for(int i=1;i<=n;i++)
        dist_min[i]=infinit;
dist_min[nod]=0;
coada.push(nod);
         while(!coada.empty())
         {
             int x1=coada.front();
             coada.pop();
             int size_=graf[x1].size();
             for(int j=0;j<size_;j++)
             {
                 int x2=graf[x1][j];
                 int cost=costuri[x1][j];
                 if(dist_min[x2]>dist_min[x1]+cost)
                 {
                  dist_min[x2]  = dist_min[x1]+cost;
                  coada.push(x2);
                 }

             }
         }
}

int main()
{
  f>>n>>m;
  for (int i=0; i<m; i++)
  {
    int x,y,z;
    f>>x>>y>>z;

    graf[x].push_back(y);
    costuri[x].push_back(z);
  }

  dijkstra(1);

  for (int j = 2; j<=n; j++)
    if(dist_min[j]==infinit)
        g<<"0";
    else g<<dist_min[j]<<" ";

  return 0;
}