#include<queue>
#include<fstream>
#include<vector>
#define N 50010
using namespace std;

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

class nod {
public:
    int a,b,c;
};

class cmp {
public:
    bool operator()(nod a, nod b) {
        return a.c>b.c;
    }
};

int n,m,dist[N];
vector<pair<int,int> > g[N];
priority_queue<nod,vector<nod>,cmp> h;

void dijkstra() {
    vector<pair<int,int> >::iterator i;
    nod t;

    while(!h.empty()) {

        while(dist[h.top().b] != -1)
            h.pop();

        dist[h.top().b] = dist[h.top().a] + h.top().c;

        t.a = h.top().b;
        for(i=g[h.top().b].begin(); i!=g[h.top().b].end(); ++i) {

            t.b = i->second;
            t.c = i->first;

            h.push(t);

        }

        h.pop();
    }

}

int main() {
    int i;
    nod t;

    in >> n >> m;

    for(i=1;i<=m;++i) {

        in >> t.a >> t.b >> t.c;

        if(t.a==1)
            h.push(t);
        else
            g[t.a].push_back(pair<int,int>(t.c,t.b));
    }

    for(i=2;i<=n;++i)
        dist[i]=-1;

    dijkstra();

    for(i=1;i<=n;++i) {
        if(dist[i]==-1)
            dist[i]=0;

        out << dist[i] << " ";

    }

    return 0;
}