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

using namespace std;

struct cmp {
    bool operator()(pair<int,int> a,pair<int,int> b) {
        return a.second>b.second;
    }
};

priority_queue<pair<int,int>, vector< pair<int,int> >, cmp> heap;
vector< pair<int,int> > v[50005];
int n,m,i,x,y,cost,nod,d[50005];
bool ok[50005];

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=2;i<=n;i++)
        d[i]=2000000000;
    for(i=1;i<=m;i++) {
        f>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
    heap.push(make_pair(1,0));
    while(!heap.empty()) {
        while(ok[heap.top().first] && !heap.empty())
            heap.pop();
        if(heap.empty())
            break;
        nod=heap.top().first;
        cost=heap.top().second;
        ok[nod]=1;
        d[nod]=cost;
        for(i=0;i<v[nod].size();i++)
            if(!ok[v[nod][i].first] && d[v[nod][i].first]>d[nod]+v[nod][i].second)
                heap.push(make_pair(v[nod][i].first,d[nod]+v[nod][i].second));
    }
    for(i=2;i<=n;i++)
        g<<(d[i]!=2000000000 ? d[i] : 0)<<" ";
    return 0;
}