#include <iostream>
#include<vector>
#include<fstream>
#include<queue>

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;
int size_, x1,x2,cost;
    for(int i=1;i<=n;i++)
        dist_min[i]=infinit;
dist_min[nod]=0;
coada.push(nod);
         while(!coada.empty())
         {
              x1=coada.front();
             coada.pop();
             size_=graf[x1].size();
             for(int j=0;j<size_;j++)
             {
                  x2=graf[x1][j];
                  cost=costuri[x1][j];
                 if(dist_min[x2]>dist_min[x1]+cost)
                 {
                  dist_min[x2]  = dist_min[x1]+cost;
                  coada.push(x2);
                 }

             }
         }
}

void afisare(int nod)
{
    for (int j = 1; j<=n; j++)
    {if(j==nod)continue;
        if(dist_min[j]==infinit)
        dist_min[j]=0;
        g<<dist_min[j]<<' ';

    }
g<<'\n';
}

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

    f>>x>>y>>z;

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


   dijkstra(1);
   afisare(1);


  return 0;
}