#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];


struct prio {
    int nod, cost;
    bool operator <(const prio& rhs) const {
        return cost > rhs.cost;
    }
};

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

void up(int start) {
    if(start == 1)
        return;
    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]);
        up(tata);
    }
}

void down(int start) {
    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]);
        down(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]);
            down(fiust);
        }
    }
}
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;
}