## solution

dijkstra。前処理等は不要で、ただ回すだけでよい。$O((N^2+M)\log N)$ではあるが十分速い。

## implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
struct state_t { int v, used, cost; };
bool operator < (state_t a, state_t b) { return make_tuple(- a.cost, - a.used, a.v) < make_tuple(- b.cost, - b.used, b.v); }
const int inf = 1e9+7;
int main() {
int n, m; cin >> n >> m;
vector<vector<vector<int> > > g(2, vector<vector<int> >(n));
repeat (i,m) {
int c, a, b; cin >> c >> a >> b;
g[c][a].push_back(b);
g[c][b].push_back(a);
}
vector<vector<int> > dp(n, vector<int>(1, inf));
priority_queue<state_t> que; {
state_t s = { 0, 0, 0 };
dp[0][0] = 0;
que.push(s);
}
while (not que.empty()) {
state_t s = que.top(); que.pop();
if (dp[s.v][s.used] < s.cost) continue;
repeat (c,2) {
for (int w : g[c][s.v]) {
state_t t;
t.v = w;
t.used = s.used + (c ? 1 : 0);
t.cost = s.cost + 1 + (c ? s.used : 0);
if (t.used >= n) continue;
auto it = min_element(dp[t.v].begin(), dp[t.v].begin() + min<int>(t.used+1, dp[t.v].size()));
if (it != dp[t.v].end() and *it <= t.cost) continue;
if (dp[t.v].size() <= t.used) dp[t.v].resize(t.used + 1, inf);
dp[t.v][t.used] = t.cost;
que.push(t);
}
}
}
repeat (i,n) {
cout << *min_element(dp[i].begin(), dp[i].end()) << endl;
}
return 0;
}