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

#define MAXN 50000
#define INF 2000000000

using namespace std;

ifstream cin( "dijkstra.in" );
ofstream cout( "dijkstra.out" );

int n, m;
int dist[MAXN+5];

struct Edge
{
  int node, d;

  bool operator <( const Edge &other ) const
  {
    return other.d<this->d;
  }
};

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

void init( int vect[] )
{
  for( int i=1;i<=n;i++ )
    vect[i]=INF;
}

void dijkstra( int source )
{
  q.push({source,0});

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

    q.pop();

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

      for( vector<Edge>::iterator it=g[t.node].begin();it!=g[t.node].end();it++ )
        q.push({it->node,t.d+it->d});
    }
  }
}

int main()
{
  cin>>n>>m;

  while( m-- )
  {
    int a, b, c;

    cin>>a>>b>>c;

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

  init(dist);

  dijkstra(1);

  for( int i=2;i<=n;i++ )
  {
    if( dist[i]==INF )
      dist[i]=0;

    cout<<dist[i]<<" ";
  }

  return 0;
}