#include <cstdio>
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
 
#define pr pair<int,int>
#define NMAX 50001
#define INF 64000
 
using namespace std;
 
vector < pr > Graf[NMAX];
int nr_nod;
int dist[NMAX];
 
struct Compare {
	
    bool operator() (const pr &a, const pr &b) const{		
        return a.second > b.second;
    }
	
};
 
priority_queue < pr, vector< pr >, Compare> Q;
 
void Read() {
    int from,to,by,muchii;
    FILE *f;
	f = fopen("dijkstra.in", "r");
	fscanf(f, "%d%d", &nr_nod, &muchii);

    for (int i = 0; i < muchii; ++i) {
        fscanf(f, "%d%d%d",  &from, &to, &by);
        Graf[from].push_back(pr(to,by));
	}   
}

void Dijkstra(int sursa) {
    int to,by,from;
    for (int i = 1; i < nr_nod+1; ++i)
        dist[i] = INF;
    dist[sursa] = 0;
    Q.push(pr(sursa,dist[sursa]));
     
    while (!Q.empty()) {
        from = Q.top().first;
        Q.pop();
        int size = Graf[from].size();
        for (int i = 0; i < size; ++i) {
            to = Graf[from][i].first;
            by = Graf[from][i].second;

            if (dist[to] > dist[from] + by) {
                dist[to] = dist[from] + by;
                Q.push(pr(to,dist[to]));
            }
        }
    }
}
void Print(){
	
	FILE *g;
	g = fopen("dijkstra.out","w");
	
    for (int i = 2; i < nr_nod+1; ++i)
        if(dist[i] == INF)
            fprintf (g, "0 ");
        else
			fprintf (g, "%d ", dist[i]);

}
int main(int argc, char const *argv[]) {
    Read();
    Dijkstra(1);
    Print();
    return 0;

}