#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector< pair <int, int > > v[50001];
int n,m,x,y,z,dist[50001],tata[50001];
bool viz[50001];
struct cmp
{ bool operator()(int x, int y) {return dist[x]>dist[y];}
};
priority_queue  <int , vector< int >, cmp> q;
void dijkstra(int start)
{ int nod,vecin,cost;
    for(int i=1;i<=n;i++)
    dist[i]=99999;
  dist[start]=0;
  q.push(start);
  while(!q.empty())
  { nod=q.top();
    q.pop();
    viz[nod]=false;
    for(int i=0;i<v[nod].size();i++)
    { vecin=v[nod][i].first;
      cost=v[nod][i].second;
      if(dist[nod]+cost<dist[vecin])
      { dist[vecin]=dist[nod]+cost;
          if(viz[vecin]==0)
          { tata[vecin]=nod;
             viz[vecin]=1;
             q.push(vecin);
          }
      }
    }
  }
}
void afisare(int j)
{ if(tata[j]==-1)
    return;
   afisare(tata[j]);
   g<<j<<" ";
}
int main()
{ f>>n>>m;
  for(int i=1;i<=m;i++)
  { f>>x>>y>>z;
      v[x].push_back({y,z});
  }
  tata[1]=-1;
  dijkstra(1);
  for(int i=2;i<=n;i++)
  { if(dist[i]!=99999)
      g<<dist[i]<<" ";
    else g<<0<<" ";
  }
    return 0;
}