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

using namespace std;

  ifstream fin("dijkstra.in");
  ofstream fout("dijkstra.out");

int n , m, a[1000000];


vector <int> v[100000];
vector <int> c[100000];
queue <int> q;

void dijkstra(int nod)
{
    for(int i=1;i<=n;i++)
      a[i]=999999999;

    q.push(nod);
    a[1]=0;

    while(!q.empty())
    {
      nod=q.front();

      for(int i=0;i<v[nod].size();i++)
        if(a[v[nod][i]]>a[nod]+c[nod][i])
        {
            a[v[nod][i]]=a[nod]+c[nod][i];
            q.push(v[nod][i]);
        }
      q.pop();
    }

}

int main()
{
    int x,y,cost;

    fin >> n >> m;

    for( int i=1; i<=m; i++ )
    {
      fin>>x>>y>>cost;
      v[x].push_back(y);
      c[x].push_back(cost);
    }

    dijkstra(1);

    for(int i=2;i<=n;i++)
    {
      if(a[i]==999999999)
        fout<<0<<' ';
      else
        fout<<a[i]<<' ';
    }

}