#include <bits/stdc++.h>
#define DIM 400001
#define log yhgfrty
#define MOD 666013

using namespace std;

ifstream fin("dijkstra.in");

ofstream fout("dijkstra.out");

vector < pair <int, int> > G[DIM];

struct nod{

    int node, val;

    bool operator < (nod x) const{

      return (x.val > val);

    };

};

int dp[DIM];

nod temp;

int n, m, x, y, z, i;

void Dijkstra(){

    priority_queue <nod> Q;

    temp.node = 1;

    temp.val = 0;

    Q.push(temp);

    dp[1] = 0;

    while(!Q.empty()){

        nod current = Q.top();

        Q.pop();

        if(dp[current.node] != current.val)

            return ;

        for(auto k : G[current.node])

            if(dp[k.first] > dp[current.node] + k.second){

                dp[k.first] = dp[current.node] + k.second;

                temp.node = k.first;

                temp.val = dp[k.first];

                Q.push(temp);

            }

    }

}

int main(){

    fin >> n >> m;

    while(m--){

        fin >> x >> y >> z;

        G[x].push_back(make_pair(y, z));

        //G[y].push_back(make_pair(x, z));

    }

    for(i=1;i<=n;i++)

        dp[i] = 2e9;

    Dijkstra();

    for(i=2;i<=n;i++)

        fout << dp[i] << " ";


}