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

#define MAXN 50000
#define INF 2.e9

using namespace std;

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

struct Edge
{
  int dest, dist;
};

class cmp
{
  public:
    bool operator() ( Edge a, Edge b )
    {
      return a.dist>b.dist;
    }
};

vector<Edge> g[MAXN+5];
priority_queue<Edge, vector<Edge>, cmp> q;

int d[MAXN+5];

int main()
{
  int n, m;

  fin>>n>>m;

  for( int i=1;i<=m;i++ )
  {
    int a, b, c;

    fin>>a>>b>>c;

    g[a].push_back(Edge{b,c});
  }

  for( int i=1;i<=n;i++ )
    d[i]=INF;

  q.push(Edge{1,0});

  while( !q.empty() )
  {
    Edge t=q.top();

    q.pop();

    if( d[t.dest]==INF )
    {
      d[t.dest]=t.dist;

      for( auto it : g[t.dest] )
        q.push(Edge{it.dest,it.dist+t.dist});
    }
  }

  for( int i=2;i<=n;i++ )
    if( d[i]!=INF )
      fout<<d[i]<<" ";
    else
      fout<<"0"<<" ";

  return 0;
}