#include <bits/stdc++.h>
#define intpair pair < int,int >
#define inf 999999
using namespace std;


ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


const int nmax = 50001;

int n,m;

vector < pair <int,int> > graf[nmax];
priority_queue < intpair , vector < intpair >, greater < intpair > >  pq;



void addedge ( int x, int y, int z)
{
    graf[x].push_back(make_pair(y,z));
    graf[y].push_back(make_pair(x,z));
}


void setup()
{
    f>>n>>m;
    int i, x,y,z;
    for(i=0 ; i < m ; i++)
    {
        f>>x>>y>>z;
        addedge(x,y,z);
    }
}


void dijkstra()
{
    pq.push(make_pair(0,1));
    vector < int > d(n,inf);
    d[1] = 0;

    while ( ! pq.empty())
    {
        int u = pq.top().second;
        pq.pop();


      vector < pair <int, int> > ::iterator it;

      for( it = graf[u].begin() ; it != graf[u].end(); it++)
      {
          int v = it->first;
          int w = it->second;

          if( d[v] > d[u] + w )
          {
              d[v] = d[u] + w;
              pq.push(make_pair(d[v], v));
          }
      }
    }

    for(int i = 2 ; i <= n ; i++)
        g << d[i] << " ";
}

int main()
{
    setup();
    dijkstra();
}