#include <fstream>
#include <queue>


using namespace std;


int best[50001];

struct nodu{
    int nod, cost;
    bool operator < ( const nodu &other )const {
        return cost > other.cost;
    }
}aux2;

priority_queue<nodu>pq;

struct muchie{
    int dest, cost;
}aux;

vector<muchie>v[50001];

int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int n, m, i, a, b, c;
    cin>>n>>m;
    for( i = 1; i <= m; i++ ) {
        cin>>a>>b>>c;
        aux.dest = b;
        aux.cost = c;
        v[a].push_back( aux );
    }
    aux2.nod = 1;
    aux2.cost = 0;
    pq.push( aux2 );
    while( !pq.empty() ) {
        aux2 = pq.top();
        pq.pop();
        a = aux2.nod;
        c = aux2.cost;
        if( best[a] == 0 ) {
            best[a] = c;
            for( i = 0; i < v[a].size(); i++ ) {
                if( best[v[a][i].dest] == 0 )  {
                    aux2.nod = v[a][i].dest;
                    aux2.cost = v[a][i].cost + c;
                    pq.push( aux2 );
                }
            }
        }
    }
    for( i = 2; i <= n; i++ ) {
        cout<<best[i]<<" ";
    }
    return 0;
}