#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50009
#define INF 999999999

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

typedef pair <int,int> edge;
#define c first
#define x second

int n,m,d[Nmax],x,y,c;
vector <edge> G[Nmax];

struct cmp {

    bool operator()(const edge &a, const edge &b) const {

        return d[a.x] > d[b.x];
    }
};

priority_queue <edge, vector<edge>, cmp> Q;

void ReadInput() {

    f>>n>>m;
    for (int i=1; i<=m; ++i) {

        f>>x>>y>>c;
        G[x].push_back(edge(c,y));

    }
}

void BFS(int node) {

    d[node]=0;
    Q.push(edge(0,node));

    while (!Q.empty()) {

        edge aux=Q.top();
        Q.pop();

        for (auto i: G[aux.x])
        {
          //  g<<i.c<<'\n';

            if (d[i.x]>d[aux.x]+i.c || d[i.x]==INF) {

                d[i.x]=d[aux.x]+i.c;
                Q.push(edge(d[i.x],i.x));
            }
        }
    }
}

void Solve() {

    for (int i=1; i<=n; ++i) d[i]=INF;

    BFS(1);

//    for (int i=1; i<=n; ++i) {
//
//        for (auto j: G[i]) g<<'('<<j.c<<' '<<j.x<<") ";
//        g<<'\n';
//    }

    for (int i=2; i<=n; ++i) g<<d[i]<<' ';
}

int main() {

    ReadInput();
    Solve();

    f.close(); g.close();
    return 0;
}