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

using namespace std;
const int NMAX = 50000;
const int INF = 21e8;

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

struct muchii {
    int nod, cost;
};
vector <vector <muchii>> v;
int dist[NMAX + 2];


int pq[NMAX + 2];
int pos[NMAX + 2];
int sizee = 0;

void up(int start) {
    while(start != 1) {
        int tata = start / 2;
        if(dist[pq[tata]] > dist[pq[start]]) { ///urcam start-ul
            swap(pos[pq[tata]], pos[pq[start]]); ///swap ca urcam
            swap(pq[tata], pq[start]);
            start = tata;
        }
        else
            return;
    }
}

void down(int start) {
    while(1) {
        int fiust = 2 * start, fiudr = 2 * start + 1;
        if(fiudr <= sizee) { ///exista ambii fii
            if(dist[pq[start]] <= dist[pq[fiust]] &&
               dist[pq[start]] <= dist[pq[fiudr]]) ///e ok
                return;
            int minn = fiust; ///luam fiul cu val <
            if(dist[pq[fiudr]] < dist[pq[fiust]])
                minn = fiudr;
            swap(pos[pq[minn]], pos[pq[start]]); ///coboram, swap
            swap(pq[minn], pq[start]);
            start = minn;
        }
        else if(fiust <= sizee) { ///are un singur fiu
            if(dist[pq[fiust]] < dist[pq[start]]) { ///swap
                swap(pos[pq[fiust]], pos[pq[start]]);
                swap(pq[fiust], pq[start]);
                start = fiust;
            }
            else
                return;
        }
        else
            return;
    }
}
void add(int id) {
    sizee++;
    pq[sizee] = id, pos[id] = sizee;
    up(id);
}

int n;
void dijkstra() {
    for(int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;

    for(int i = 1; i <= n; i++) ///si cu inf, doar sa fie adaugate
        add(i);
    for(int z = 1; z <= n; z++) {
        int now = pq[1];
        if(dist[now] == INF) ///asta e minimul --> stop, nu mai avem
            return;
        ///scoatem
        pq[1] = pq[sizee];
        pos[pq[1]] = 1;
        sizee--;
        if(!sizee) ///caz special, nu mai ai nr
            return;
        down(1); ///ca DOAR scade
        for(auto x : v[now]) {
            if(dist[x.nod] > dist[now] + x.cost) { ///replace la val veche in heap
                dist[x.nod] = dist[now] + x.cost;
                up(pos[x.nod]); ///ar trebui DOAR mai sus (ca e mai mic)
            }
        }
    }
}

int main()
{
    int m;
    cin >> n >> m;
    v.resize(n + 1);
    for(int i = 1; i <= m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        v[a].push_back({b, cost});
    }
    dijkstra();
    for(int i = 2; i <= n; i++) {
        if(dist[i] == INF)
            dist[i] = 0;
        cout << dist[i] << " ";
    }
    return 0;
}