#include <cstdio>
#include <set>
#include <vector>
#include <climits>

using namespace std;

#define NMAX 50001

int Dist[NMAX];
set < pair < int , int > > Q;
vector < pair < int , int > > L[NMAX];
int x,y,c,i,N,M;

void Dijkstra()
{
    Q.insert(make_pair(1,0));

    for (int i=2;i<=N;++i) Dist[i]=INT_MAX;

    while (Q.size()>0)
      {
          pair < int , int > aux=(*(Q.begin()));
          Q.erase(*(Q.begin()));

          for (vector < pair < int , int > > :: iterator it=L[aux.first].begin();it!=L[aux.first].end();++it)
             {
                  if (Dist[(*it).first]<=aux.second+(*it).second) continue;

                  Dist[(*it).first]=aux.second+(*it).second;

                  Q.insert(make_pair((*it).first,Dist[(*it).first]));
             }
      }
}

int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);

scanf("%d%d",&N,&M);
for (i=1;i<=M;++i)
  {
      scanf("%d%d%d",&x,&y,&c);
      L[x].push_back(make_pair(y,c));
  }

Dijkstra();

for (i=2;i<=N;++i) (Dist[i]==INT_MAX) ? printf("0 ") : printf("%d ",Dist[i]);

return 0;
}