#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

ofstream fo("dijkstra.out");
ifstream fi("dijkstra.in");
struct arc
{
    int a,lungime;
};

bool operator <(arc a1,arc a2)
{

  if(a1.lungime>a2.lungime)
    return true;

  return false;
}

int n,m,x1,x2,L;
int drum[50005];
bool viz[50005];
vector<arc> vecini[50005];
priority_queue<arc> coada;
arc citit;


int main()
{

    fi>>n>>m;

    for(int i=1; i<=m; i++)
    {
      fi>>x1>>x2>>L;
      citit.a=x2;
      citit.lungime=L;
      vecini[x1].push_back(citit);

        drum[i]= 0x3f3f3f3f;
    }



arc pornire;
pornire.a=1;
drum[1]=0;
pornire.lungime=0;
coada.push(pornire);


while(!coada.empty())
{
  arc curent=coada.top();
  coada.pop();


  for(auto vecin:vecini[curent.a] )/// merg pe vecini
  {
    if(drum[vecin.a]>drum[curent.a]+vecin.lungime)
    {

    drum[vecin.a]=drum[curent.a]+vecin.lungime;
    coada.push(vecin);
    }
  }


}


for(int i=2;i<=n;i++)
fo<<drum[i]<<" ";

    return 0;
}