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

using namespace std;

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

int n,m,a,b,c;
int dist[50002], coada[50002];
short viz[50002];

struct arc {
    int destinatie;
    short cos;
};
arc element;

vector <arc> graph[50002];
priority_queue <pair <short, int> > myheap;

void dijkstra(){
    while (!myheap.empty()){
        pair <short,int> curent=myheap.top();
        int nod=curent.second;
        short costInit=-curent.first;
        if (viz[nod]!=1){
            viz[nod]=1;
            dist[nod]=costInit;
            int lun=graph[nod].size();
            for (int i=0; i<lun; i++){
                int vecin=graph[nod][i].destinatie;
                short cost=graph[nod][i].cos;
                myheap.push(make_pair(-(cost+costInit),vecin));
                if (cost+costInit<dist[vecin]){
                    dist[vecin]=cost+costInit;
                }
            }
        }
        myheap.pop();
    }
}

void initMax (int a[]){
    for (int i=2; i<=50001; i++){
        a[i]=0;
    }
}

int main () {

    fin>>n>>m;

    for (int i=1; i<=m; i++){
        fin>>a>>b>>c;
        element.destinatie=b;
        element.cos=c;
        graph[a].push_back(element);
    }

    initMax (dist);

    myheap.push(make_pair(0,1));
    dijkstra();

    for (int i=2; i<=n; i++){
        fout<<dist[i]<<' ';
    }

    return 0;
}