#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
#define FILEIN "dijkstra.in"
#define FILEOUT "dijkstra.out"
 
const int MAXN = 50005;
const int INF = 0x3f3f3f3f;
 
int N, M;
vector< pair<int, int> > G[MAXN];
int Dmin[MAXN];
 
void ReadData() {
    ifstream fin(FILEIN);
 
    fin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int a, b, c;
 
        fin >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }
}
 
void Solve() {
    bool InQueue[MAXN];
    queue<int> Q;
 
    memset(Dmin, INF, sizeof(Dmin));
    memset(InQueue, false, sizeof(InQueue));
 
    Dmin[1] = 0;
    Q.push(1);
    InQueue[1] = true;
 
    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        InQueue[nod] = false;
 
        for (vector< pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
                if (!InQueue[it->first]) {
            if (Dmin[nod] + it->second < Dmin[it->first]) {
                Dmin[it->first] = Dmin[nod] + it->second;
                    Q.push(it->first);
                    InQueue[it->first] = true;
                }
            }
    }
}
 
void WriteData() {
    ofstream fout(FILEOUT);
 
    for (int i = 2; i <= N; ++i)
        fout << (Dmin[i] < INF ? Dmin[i] : 0) << " ";
}
 
int main() {
    ReadData();
    Solve();
    WriteData();
}