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

#define NM 100001
#define INF 2000000000

using namespace std;

ifstream hai("dijkstra.in");
ofstream pa("dijkstra.out");

int d[NM], n, m ,p;
bool inq[NM];

struct Arch{
  int y, dist;
};

vector<Arch> G[NM];

struct Comp{
  bool operator()(int x, int y){
    return d[x]>d[y];
  }
};

priority_queue<int, vector<int>, Comp> q;

void Dijkstra(int x){
  int i, j, k, len, y, dist;
  for(i = 1; i <= n; i++)
      d[i] = INF;
  d[x] = 0;
  q.push(x);
  inq[x] = 1;
  while(!q.empty())
    {
        k=q.top();
        q.pop();
        inq[k]=0;
        for(j=0;j<G[k].size();j++)
        {
            y=G[k][j].y;
            dist=G[k][j].dist;
            len=d[k]+dist;
            if(len<d[y])
            {
                d[y]=len;
                if(inq[y]==0)
                {
                    q.push(y);
                    inq[y]=1;
                }
            }
        }
    }
}

int main(){

  int i;
  hai >> n >> m ;
  for(i = 1; i <= m; i++){
    int x;
    Arch u;
    hai >> x >> u.y >> u.dist;
    G[x].push_back(u);
  }
  Dijkstra(1);
  for(i = 2; i <= n; i++){
    if(d[i]!=INF)
      pa << d[i] << " ";
    else
      pa << 0 << " ";
  }
}