#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define inf 1000000000
#define Nmax 50001
using namespace std;

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

vector < pair<int,int> >graf[Nmax];
int drum[Nmax],minim[Nmax];

void dijkstra(set <pair<int,int> >nod) {
     int distance,target,node;
     while(!nod.empty()) {
          node=nod.begin() -> second;
          int length=graf[node].size();
          nod.erase(nod.begin());
          for(int i=0;i<length;i++) {
              target=graf[node][i].first;
              distance=graf[node][i].second;
              if(drum[target] > drum[node]+distance) {
                    if(drum[target]!=inf)
                       nod.erase(nod.find(pair<int,int >(drum[target],target)));
                drum[target]=drum[node]+distance;
                nod.insert(make_pair(drum[target],target));
            }
        }
     }

}

int main()
{
    int n,m,nod1,nod2,dist;
    f>>n>>m;
    for(int i=1;i<=m;i++) {
        f>>nod1>>nod2>>dist;
        graf[nod1].push_back(make_pair(nod2,dist));
    }
    for(int i=2;i<=n;i++)
        drum[i]=inf;
    set<pair<int,int> >nod;
    nod.insert(make_pair(0,1));
    dijkstra(nod);
    for(int i=2;i<=n;i++)
        if(drum[i]!=inf)
          g<<drum[i]<<" ";
         else
            g<<0<<" ";
    return 0;
}