#include <bits/stdc++.h>
#define NMAX 50009
#define INF 9999999
#define ll long long int
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m;
int d[NMAX];
bool uz[NMAX];

struct nume{int x;};
struct nume1{int   y;int c;};
vector <nume1>g[NMAX];
bool operator <(nume a, nume b)
{
    return d[a.x]>d[b.x];
}
priority_queue<nume>H;

void citire();
void djk(int start);
void afisare();
int main()
{citire();
djk(1);
afisare();
    return 0;
}
void citire()
{int i,j,x,y,c;
  fin>>n>>m;
  for(i=1;i<=m;i++)
        {
        fin>>x>>y>>c;
        g[x].push_back({y,c});
        //g[y].push_back({x,c});

        }
}
void djk(int start)
{ nume act;
  nume1 vec;
  int i;
  for(i=1;i<NMAX;i++)
        d[i]=INF;
  d[start]=0;uz[start]=1;H.push({start});
  while(!H.empty())
        {
        act=H.top();H.pop();uz[act.x]=0;
        for(i=0;i<g[act.x].size();i++)
            {
            vec=g[act.x][i];
            if(d[act.x]+vec.c<d[vec.y])
               {d[vec.y]=d[act.x]+vec.c;
                uz[vec.y]=1;
                H.push({vec.y});
               }
            }
        }
}
void afisare()
{
int i;
for(i=2;i<=n;i++)
        if(d[i]!=INF)
           fout<<d[i]<<" ";
     else
        fout<<0<<" ";
}