include[HTML_REMOVED]

using namespace std;
const int INF = INT_MAX;
int n, m;
int main() {
freopen(“paths.in”,”r”,stdin);
freopen(“paths.out”,”w”,stdout);
cin >> n >> m;
vector[HTML_REMOVED]> g(n, vector[HTML_REMOVED](n, INF));
for (int i = 0; i < n; i) {
for (int j = 0; j < n; j) {
if (i!= j) {
g[i][j] = abs(i - j);
}
}
}
for (int i = 0; i < m; i) {
int u, v, w;
cin >> u >> v >> w;
g[u - 1][v - 1] = min(g[u - 1][v - 1], w);
g[v - 1][u - 1] = min(g[v - 1][u - 1], w);
}
vector[HTML_REMOVED] dist(n, INF);
dist[0] = 0;
for (int k = 0; k < n; k) {
for (int i = 0; i < n; i) {
for (int j = 0; j < n; j) {
if (dist[i]!= INF && g[i][j]!= INF) {
dist[j] = min(dist[j], dist[i] + g[i][j]);
}
}
}
}
for (int i = 1; i < n; i++) {
cout << dist[i] << ” “;
}
cout << endl;
return 0;
}