#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
#define pli pair<long long, int>
#define fi first
#define sc second
#define BIT(x, i) ((x >> i) & 1)
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define file ""
 
const int N = 1e5+5;
const int LOG = 20;
const int MOD = 1e9+7;
const ll INF = 1e18;
 
int n, m;
vector<pii> a[N];
 
void dijsktra(){
    vector<ll> d(n + 1, INF);
    priority_queue<pli, vector<pli>, greater<pli>> q;
    d[1] = 0;
    q.push({0, 1});
    while(!q.empty()){
        pli top = q.top();
        q.pop();
        int u = top.second;
        int dis = top.first;
        if (dis > d[u])
            continue;
        for (pii p : a[u]){
            int v = p.first;
            int w = p.second;
            if (d[v] > d[u] + w){
                d[v] = d[u] + w;
                q.push({d[v], v});
            }
        }
    }
    FOR(i, 1, n){
        cout << d[i] << ' ';
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);   cin.tie(0); cout.tie(0);
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    cin >> n >> m;
    FOR(i, 1, m){
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
    }
    dijsktra();
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgdWxsIHVuc2lnbmVkIGxvbmcgbG9uZwojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIHBpaSBwYWlyPGludCwgaW50PgojZGVmaW5lIHBsaSBwYWlyPGxvbmcgbG9uZywgaW50PgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Mgc2Vjb25kCiNkZWZpbmUgQklUKHgsIGkpICgoeCA+PiBpKSAmIDEpCiNkZWZpbmUgZWIoeCkgZW1wbGFjZV9iYWNrKHgpCiNkZWZpbmUgcGIoeCkgcHVzaF9iYWNrKHgpCiNkZWZpbmUgcGYoeCkgcHVzaF9mcm9udCh4KQojZGVmaW5lIEZPUihpLCBhLCBiKSBmb3IoaW50IGkgPSBhOyBpIDw9IGI7IGkrKykKI2RlZmluZSBGT1JEKGksIGEsIGIpIGZvciAoaW50IGkgPSBhOyBpID49IGI7IGktLSkKI2RlZmluZSBmaWxlICIiCiAKY29uc3QgaW50IE4gPSAxZTUrNTsKY29uc3QgaW50IExPRyA9IDIwOwpjb25zdCBpbnQgTU9EID0gMWU5Kzc7CmNvbnN0IGxsIElORiA9IDFlMTg7CiAKaW50IG4sIG07CnZlY3RvcjxwaWk+IGFbTl07CiAKdm9pZCBkaWpza3RyYSgpewogICAgdmVjdG9yPGxsPiBkKG4gKyAxLCBJTkYpOwogICAgcHJpb3JpdHlfcXVldWU8cGxpLCB2ZWN0b3I8cGxpPiwgZ3JlYXRlcjxwbGk+PiBxOwogICAgZFsxXSA9IDA7CiAgICBxLnB1c2goezAsIDF9KTsKICAgIHdoaWxlKCFxLmVtcHR5KCkpewogICAgICAgIHBsaSB0b3AgPSBxLnRvcCgpOwogICAgICAgIHEucG9wKCk7CiAgICAgICAgaW50IHUgPSB0b3Auc2Vjb25kOwogICAgICAgIGludCBkaXMgPSB0b3AuZmlyc3Q7CiAgICAgICAgaWYgKGRpcyA+IGRbdV0pCiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIGZvciAocGlpIHAgOiBhW3VdKXsKICAgICAgICAgICAgaW50IHYgPSBwLmZpcnN0OwogICAgICAgICAgICBpbnQgdyA9IHAuc2Vjb25kOwogICAgICAgICAgICBpZiAoZFt2XSA+IGRbdV0gKyB3KXsKICAgICAgICAgICAgICAgIGRbdl0gPSBkW3VdICsgdzsKICAgICAgICAgICAgICAgIHEucHVzaCh7ZFt2XSwgdn0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgRk9SKGksIDEsIG4pewogICAgICAgIGNvdXQgPDwgZFtpXSA8PCAnICc7CiAgICB9Cn0KIAppbnQgbWFpbigpewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsgICBjaW4udGllKDApOyBjb3V0LnRpZSgwKTsKICAgIC8vZnJlb3BlbihmaWxlIi5pbnAiLCAiciIsIHN0ZGluKTsKICAgIC8vZnJlb3BlbihmaWxlIi5vdXQiLCAidyIsIHN0ZG91dCk7CiAgICBjaW4gPj4gbiA+PiBtOwogICAgRk9SKGksIDEsIG0pewogICAgICAgIGludCB1LCB2LCB3OwogICAgICAgIGNpbiA+PiB1ID4+IHYgPj4gdzsKICAgICAgICBhW3VdLnB1c2hfYmFjayh7diwgd30pOwogICAgfQogICAgZGlqc2t0cmEoKTsKICAgIHJldHVybiAwOwp9Cg==

MTAgMjAgMSAzIDc0MiAyIDUgNjEzIDMgOSA4MDUgNCAxIDI5NiA1IDEwIDkzNCA2IDIgNDcxIDcgNCA4ODggOCA2IDEyMyA5IDcgNjkwIDEwIDggNTU3IDIgMyA0MTggMyA2IDczMSA0IDkgMjY1IDUgNyA1NDkgNiAxMCA5MDIgNyAxIDM3NyA4IDIgODQ1IDkgNSA2MDggMTAgMyA3OTEgMSA5IDM1Ng==

10 20 1 3 742 2 5 613 3 9 805 4 1 296 5 10 934 6 2 471 7 4 888 8 6 123 9 7 690 10 8 557 2 3 418 3 6 731 4 9 265 5 7 549 6 10 902 7 1 377 8 2 845 9 5 608 10 3 791 1 9 356