#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMAX=50001;
const int INF=1000000000;
int n,m;
int dist[NMAX];

vector < pair < int,int > > D[NMAX];

void read()
{
    int x,y,c;
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        D[x].push_back(make_pair(y,c));
    }

}

void d(int p)
{
  int dmin=INF,imin,imin2;
  bool viz[NMAX]={0};
  dist[p]=0;

  for(int i=1;i<=n;++i) dist[i]=INF;

  for(int i=0;i<D[p].size();++i)
  {
      dist[D[p][i].first]=D[p][i].second;
      if(D[p][i].second<dmin)
        {
            dmin=D[p][i].second;
            imin=D[p][i].first;
        }
  }
  viz[p]=1;

  bool ok=1;

  while(ok)
  {
    ok=0;
    dmin=INF;
    viz[imin]=1;
    for(int i=0;i<D[imin].size();++i)
        if(viz[D[imin][i].first]==0)
            if(D[imin][i].second<dmin)
            {
               if(dist[D[imin][i].first]>(dist[imin]+D[imin][i].second))
                    dist[D[imin][i].first]=dist[imin]+D[imin][i].second;
               dmin=D[imin][i].second;
               imin2=D[imin][i].first;
               ok=1;
            }
    imin=imin2;
  }
}

void r(int p)
{
  int dmin=INF,imin,imin2;
  bool viz[NMAX]={0};

  viz[p]=1;

  bool ok=1;

  imin=p;

  while(ok)
  {

    ok=0;
    dmin=INF;
    viz[imin]=1;
    for(int i=0;i<D[imin].size();++i)
        if(viz[D[imin][i].first]==0)
            if(D[imin][i].second<dmin)
            {
               if(dist[D[imin][i].first]>(dist[imin]+D[imin][i].second))
                    dist[D[imin][i].first]=dist[imin]+D[imin][i].second;
               dmin=D[imin][i].second;
               imin2=D[imin][i].first;
               ok=1;
            }
    imin=imin2;
  }

}


int main()
{
    read();
    d(1);
    for(int i=2;i<=n;++i) r(i);
    for(int i=2;i<=n;++i) if(dist[i]==INF) fout<<0<<" "; else fout<<dist[i]<<" ";
    return 0;
}