#include <fstream>
#include <queue>
#include <vector>

using namespace std;

priority_queue < pair <int,int> > pq;
vector < pair <int,int> > v[50001];
bool viz[50001];
int ans[50001];
pair<int,int>p;

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

void dijkstra ()
{

  pq.push({0,1});
  while (!pq.empty())
  {
    p=pq.top();
    pq.pop();
    swap(p.first,p.second);
    p.second=-p.second;
    if (ans[p.first]<p.second&&viz[p.first])
        continue;
    int nod,dist;
    for (int i=0;i<v[p.first].size();++i)
    {
      nod=v[p.first][i].second;//nodul a fost pus pe pozitia a doua
      dist=v[p.first][i].first; //distanta dintre nodul anterior si cel curent
      if (viz[nod]&&ans[nod]<=p.second+dist)
         continue;
      pq.push({-dist-p.second,nod}); //punem in pq distanta cu minus ca sa iasa in fata
      viz[nod]=1;
      ans[nod]=dist+p.second;
    }
  }
}

int main()
{
    int n,m,a,b,c;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
      in>>a>>b>>c;
      v[a].push_back({c,b});
    }
    dijkstra();
    for (int i=2;i<=n;i++)
       out<<ans[i]<<" ";
    return 0;
}