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

using namespace std;
const int inf = (1 << 30);
long n,viz[50001]={0},dist[50001]={0};
vector<pair<int,int>>graf[50001];

void dijkstra()
{
   long vmin,index,j,i;
  for(i=1;i<=n;i++)
  {
    vmin=inf;
   for(j=1;j<=n;j++)
    if(dist[j]<vmin && viz[j]==0)
        {vmin=dist[j];
        index=j;}

    /*
    int lim = graph[index].size();
    for(int i = 0; i < lim; i++) {
        int vecin = graph[index][i];
    }
    */
    vector<pair<int,int>>::iterator it;
    for(it = graf[index].begin(); it !=graf[index].end(); it++ )
    {

        if(dist[(*it).first]>dist[j]+(*it).second)
         dist[(*it).first]=dist[j]+(*it).second;

    }
  }
}


int main()
{
    long m,i,x,y,cost;
    ifstream f ("dijkstra.in");
    f>>n>>m;
    for(i=2;i<=n;i++)
        dist[i]=inf;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>cost;
        graf[x].push_back(make_pair(y,cost));
    }
    dijkstra();
    for(i=1;i<=n;i++)
        cout<<dist[i]<<" ";
    return 0;
}