#include <fstream>
#include <vector>
#include <queue>
#define MAX 50005
#define INF 1<<30
using namespace std;
struct data{
int edge, weight;
} nd;
vector<data> v[MAX];
int nodes, edges, distances[MAX];
int initial_point(1), vs;
bool visited[MAX];
void scan();
void solve();
int minQ();
void write();
int main(){
scan();
solve();
write();
return 0;
}
void scan(){
ifstream fin ("dijkstra.in");
fin >> nodes >> edges;
int x, y, z, m = edges;
while(m--){
fin >> x >> y >> z;
nd.edge = y, nd.weight = z;
v[x].push_back(nd);
}
for (int i = 1; i <= nodes; ++i)
distances[i] = INF;
fin.close();
}
void solve(){
distances[initial_point] = 0;
while(vs != nodes){
int k = minQ();
for (unsigned int i = 0; i < v[k].size(); ++i)
if (distances[v[k][i].edge] > distances[k] + v[k][i].weight)
distances[v[k][i].edge] = distances[k] + v[k][i].weight;
}
}
int minQ(){
int mn = INF, k;
for (int i = 1; i < nodes; ++i)
if (distances[i] < mn && !visited[i])
mn = distances[i],
k = i;
visited[k] = 1;
++vs;
return k;
}
void write(){
ofstream fout ("dijkstra.out");
for (int i = 1; i <= nodes; ++i)
if (i == initial_point)
continue;
else fout << (distances[i] == INF ? 0 : distances[i]) << " ";
fout.close();
}