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

using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

#define INF 0x3f3f3f3f
#define MAXN 50005

struct grf {
    int nod, cost;
}act, aux;

class comp {
public:
    bool operator() ( grf A, grf B ) {
        return A.cost > B.cost;
    }
};

vector<grf> graf[MAXN];
priority_queue<grf, vector<grf>, comp> coada;
int d[MAXN];
int n, m;

int main() {
    int i, x;
    cin >> n >> m;
    
    for(i=1; i<=m; i++) {
        cin >> x >> aux.nod >> aux.cost;
        graf[x].push_back(aux);
    }
    
    for(i=1; i<=n; i++)
        d[i] = INF;
    
    d[1] = 0;
    aux.nod = 1; aux.cost = 0;
    coada.push(aux);
    
    while(!coada.empty()) {
        act = coada.top(); coada.pop();
        if( act.cost != d[act.nod] )
            continue;
        
        for(i=0; i<graf[act.nod].size(); i++) {
            if( d[ graf[act.nod][i].nod ] > act.cost + graf[act.nod][i].cost ) {
                d[ graf[act.nod][i].nod ] = act.cost + graf[act.nod][i].cost;
                aux.nod = graf[act.nod][i].nod;
                aux.cost = d[ graf[act.nod][i].nod ];
                
                coada.push(aux);
            }
        }
    }
    
    for(i=2; i<=n; i++)
        if(d[i] == INF)
            cout<<"0 ";
        else
            cout<<d[i]<<" ";
    
    return 0;
}