#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];
short viz[50002];

struct arc {
    int destinatie;
    int cos;
};

arc element;

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

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

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);
    }

    for (int i=2; i<=50001; i++){
        dist[i]=2000000000;
    }

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

    for (int i=2; i<=n; i++){
        if (dist[i]!=2000000000){
            fout<<dist[i]<<' ';
        }
        else{
            fout<<"0 ";
        }
    }

    return 0;
}