#include <iostream>
#include <vector>
#include <utility>
#include <fstream>

#define NMAX 50001
#define INF 20001
using namespace std;

vector < pair <int,int> > vecini[NMAX];
int vizitat[NMAX];
int distante[NMAX];
vector <int> set;

int alege_minim(int n){
    int minim = INF;
    int nod;
    int ok=1;
    for(int i=1;i<=n;i++){
        ok=1;
        if( set.empty() == 0 )
            for(int j=0;j<=set.size();j++)
                if(set[j]==i)ok=0;

        if(ok == 1){
            if(distante[i]<minim)
                nod = i;
        }
    }
    return nod;
}

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

    int n,m,a,b,c;

    f>>n>>m;

    for(int i=0;i<m;i++){
        f>>a>>b>>c;
        vecini[a].push_back( make_pair(c,b) ) ;
    }
    for(int i=1;i<=n;i++){
        distante[i]=INF;
    }

    //cout<<vecini[1][1].second<< "      " <<vecini[1][1].first<<endl;

    //Calculam incepand de la nodul 1;
    distante[1]=0;


    while(set.size()<n){
        int nod = alege_minim(n);
        set.push_back(nod);
        for(int i=0;i<vecini[nod].size();i++){
            if( distante[vecini[nod][i].second]  >  distante[nod]+vecini[nod][i].first  )
                distante[vecini[nod][i].second] = distante[nod]+vecini[nod][i].first;
        }
    }

    for(int i=2;i<=n;i++){
        if(distante[i]==INF)
            g<<0<<" ";
        else
            g<<distante[i]<<" ";
    }


    return 0;
}

//#include <iostream>
//#include <fstream>
//#include <vector>
//#include <utility>
//#define NMAX 50001
//#define INF 20001
//
//using namespace std;
//
//vector<int>dist;
//vector<int>viz;
//vector< pair<int,int> >graf[NMAX];
//
//int nevizitat_mic(){
//    int minim=INF;
//    int nr;
//    for(int i=1;i<(int)dist.size();i++)
//    {
//        if(dist[i]<minim)
//            if(viz[i]==0)
//            {
//                minim = dist[i];
//                nr = i;
//            }
//    }
//    return nr;
//}
//
//void dijkstra(int index)
//{
//    for(int i=0;i<(int)graf[index].size();i++)
//    {
//        if(dist[index] + graf[index][i].second < dist[graf[index][i].first])
//            dist[ graf[index][i].first ] = dist[index] + graf[index][i].second;
//    }
//    viz[index] = 1;
//
//
//}
//
//int main()
//{
//    ifstream f("dijkstra.in");
//    ofstream g("dijkstra.out");
//
//    int n,m;
//    int a,b,d;
//    f>>n>>m;
//    for(int i=0;i<m;i++){
//        f>>a>>b>>d;
//        graf[a].push_back(make_pair(b,d));
//    }
//
//    for(int i=0;i<=n;i++){
//        dist.push_back(INF);
//    }
//    for(int i=0;i<=n;i++){
//        viz.push_back(0);
//    }
//
//    dist[1]=0;
//
//    for(int i=0;i<n;i++){
//        dijkstra(nevizitat_mic());
//    }
//
//    for(int i=2;i<=n;i++)
//        if(dist[i] == INF)
//            g<<0<<" ";
//        else
//            g<<dist[i]<<" ";
//
//
//    return 0;
//}