#include <fstream>
#include <vector>
#include <queue>
#define LE 50666
using namespace std;
ifstream f("dijkstra.in");ofstream g("dijkstra.out");
int n,m,i,j,cc,result[LE],xx,yy;
bool viz[LE];
#define mp make_pair
#define pb push_back
#include <vector>
#define x first
#define y second
vector<pair<int,int> > H[LE];
struct comp{
 bool operator()(pair<int,int> aa,pair<int,int>bb){
   return aa.x>bb.x;
 }
};
struct two{int xxe,yye;};
priority_queue < pair<int,int >,  vector<pair<int,int> >,comp  >que;

int main(){
    f>>n>>m;que.push(mp(0,1));
    for(i=1;i<=m;++i) {f>>xx>>yy>>cc;H[xx].pb(mp(yy,cc));}

    while (que.empty()==false){

      pair<int,int> node=que.top();que.pop();
      if (viz[node.y]==true) continue;
      int N=H[node.y].size(); viz[node.y]=true; result[node.y]=node.x;

      for(i=0;i<N;++i)
        if (viz[H[node.y][i].x]==false)
          que.push(mp(node.x+H[node.y][i].y,H[node.y][i].x));
    }

    for(i=2;i<=n;++i) g<<result[i]<<" ";

    f.close();g.close();
    return 0;
}