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

using namespace std;

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


const int NMAX = 50008;
const int INF = 100000000;

int N; int M;int dist[NMAX];

struct Node{

    int Cost; int V;

    Node(){
        this -> Cost = 0;
        this -> V = 0;
    }

    Node(int V, int Cost){
        this -> Cost = Cost;
        this -> V = V;
    }
    bool operator<(Node Y) const{
        return  this -> Cost > Y.Cost;
    }
};

vector <Node> G[NMAX];

void Read(){

    fin >>N >> M;
    for(int i = 1; i <= M; ++i) {
        int x; int y; int cost;
        fin >> x >> y >> cost;
        G[x].push_back(Node(y,cost));
    }
}

void Dijkstra(Node S){

    for(int i = 0 ;i <= N; ++i) dist[i] = INF;

    dist[S.V] = 0;
    priority_queue<Node> Q;
    Q.push(Node(S.V, 0));

    while(!Q.empty()){
        int X = Q.top().V;
        Q.pop();

        for(int i = 0 ;i < G[X].size(); ++i){
            int nod = G[X][i].V;
            int c = G[X][i].Cost + dist[X];
            if(dist[nod] > c){
                dist[nod] = c;
                Q.push(Node(nod, c));

            }
        }
    }

}
int main(){

    Read ();

    Dijkstra(Node(1,0));
    for(int i = 2 ; i <= N; ++i)
        fout << ((dist[i] == INF) ? 0 : dist[i] )<<" ";

    return 0;
}