#include<stdio.h>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
FILE*fin=fopen("dijkstra.in","r");
FILE*fout=fopen("dijkstra.out","w");
#define nm 50005
#define mkp make_pair
#define pb push_back
#define inf 1000000000
vector<pair<int,int> > g[nm];
queue<int> q;
char inside[nm];
int n,m,dmin[nm];
int main()
{
  int i,a,b,c,nod,nnod;  
  fscanf(fin,"%d%d",&n,&m);
  for(i=1;i<=m;i++)  
  {
    fscanf(fin,"%d%d%d",&a,&b,&c);
    g[a].pb(mkp(b,c));
  }
  memset(inside,0,sizeof(inside));
  for(i=1;i<=n;i++)
    dmin[i]=inf;
  inside[1]=1;
  q.push(1);
  dmin[1]=0;
  while(!q.empty())
  {
    nod=q.front();
    q.pop();
    inside[nod]=0;
    for(i=0;i<g[nod].size();i++)
    {
      nnod=g[nod][i].first;
      if(dmin[nod]+g[nod][i].second<dmin[nnod])
      {
        dmin[nnod]=dmin[nod]+g[nod][i].second;
        if(!inside[nnod])
        {
          inside[nnod]=1;
          q.push(nnod);
        }
      }
    }
  }
  for(i=2;i<=n;i++)
    if(dmin[i]==1000000000) fprintf(fout,"0 ");
    else fprintf(fout,"%d ",dmin[i]);
  fclose(fin);
  fclose(fout);
  return 0;
}