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

using namespace std;

#define NMAX 50005

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.empty())
      {
          for (vector < pair < int , int > > :: iterator it=L[(*Q.begin()).first].begin();it!=L[(*Q.begin()).first].end();++it)
             {
                  if (Dist[(*it).first]<=(*Q.begin()).first+(*it).second) continue;
                  Dist[(*it).first]=(*Q.begin()).second+(*it).second;
                  Q.insert(make_pair((*it).first,Dist[(*it).first]));
             }
          Q.erase(*(Q.begin()));
      }
}

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;
}