#include<fstream>
#include<vector>
#include<set>

using namespace std;

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

const int Nmax=50000,oo=2000000000;
vector <pair <int, int> > G[Nmax+5];
set <pair <int, int> > Heap;
int N,M,DP[Nmax+5];

void Dijkstra(){
    for(int i=2;i<=N;i++)
        DP[i]=oo;
    Heap.insert({1,0});
    while(!Heap.empty()){
        pair <int, int> Nod=*Heap.begin();
        Heap.erase(Heap.begin());
        for(auto i:G[Nod.first]){
            if(DP[i.first]>DP[Nod.first]+i.second){
                if(DP[i.first]!=oo)
                   Heap.erase(Heap.find({i.first,DP[i.first]}));
                DP[i.first]=DP[Nod.first]+i.second;
                Heap.insert({i.first,DP[i.first]});
            }
        }
    }
    for(int i=2;i<=N;i++)
        fout<<DP[i]<<" ";
    fout<<'\n';
}

int main(){
    fin>>N>>M;
    for(int i=1;i<=M;i++){
        int X,Y,Z;
        fin>>X>>Y>>Z;
        G[X].push_back({Y,Z});
    }
    Dijkstra();
}