#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 a.c > b.c;
    }
};
 
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 Dijkstra(int S) {
    for (int i=1; i<=n; ++i) d[i]=INF; 
    d[S] = 0;
    Q.push(edge(0, S));
 
    while (!Q.empty()) {
        edge aux=Q.top();
        int node = aux.x;
        int cost = aux.c;
        Q.pop();

        if (cost > d[node]) {
            continue;
        }
  
        for (auto it: G[node]) {
            int x = it.x;
            int c = it.c;

            if (d[node] + c < d[x] || d[x]==INF) {
                d[x] = d[node] + c;
                Q.push(edge(d[x], x));
            }
        }
    }
}
 
void Solve() {
    Dijkstra(1);
    for (int i=2; i<=n; ++i) g<<(d[i] < INF ? d[i] : 0)<<' ';
}

int main() {
    ReadInput();
    Solve();
 
    f.close(); g.close();
    return 0;
}