#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int VSIZE = 50005;
const int INF = 2000000000;
int N,M;
int minDistance[VSIZE];
bool isChecked[VSIZE];

struct el
{
    int node,cost;
    bool operator < (const el &A) const{
        return cost > A.cost;
    }
};

vector < el > L[VSIZE];
priority_queue < el > Q;


inline void Read()
{
    int x;
    el w;
    fin >> N >> M;
    for(int i = 1; i <= M; i++) {
        fin >> x >> w.node >> w.cost;
        L[x].push_back(w);
    }
}

inline void Dijkstra()
{
    int cost,nnode;
    for(int i = 2; i <= N; i++) {
        minDistance[i] = INF;
    }
    el w,w2;
    w.node = 1, w.cost = 0; Q.push(w);
    while(!Q.empty())
    {
        w = Q.top(); Q.pop();
        if(isChecked[w.node]) continue;
        isChecked[w.node] = true;
        for(auto it : L[w.node])
        {
            nnode = it.node;
            cost = it.cost + minDistance[w.node];
            if(minDistance[nnode] > cost) {
                minDistance[nnode]= cost;
                w2.node = nnode; w2.cost = minDistance[nnode];
                Q.push(w2);
            }
        }
    }
}


inline void Print()
{
    for(int i = 2; i <= N; i++){
        fout << (minDistance[i] == INF? 0 : minDistance[i]) << " ";
    }
    fout << "\n";
    fout.close();
}

int main()
{
    Read();
    Dijkstra();
    Print();
    return 0;
}