#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1000005;
vector<int> g[MAXN];
int dist[MAXN];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, C;
    cin >> N >> C;
 
    for (int i = 1; i <= C; i++) {
        int Ei, B1, B2;
        cin >> Ei >> B1 >> B2;
        g[Ei].push_back(B1);
        g[Ei].push_back(B2);
    }
 
    queue<int> q;
    q.push(1);
    dist[1] = 1;
 
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
 
    for (int i = 1; i <= N; i++)
        cout << dist[i] << "\n";
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTUFYTiA9IDEwMDAwMDU7CnZlY3RvcjxpbnQ+IGdbTUFYTl07CmludCBkaXN0W01BWE5dOwoKaW50IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwoKICAgIGludCBOLCBDOwogICAgY2luID4+IE4gPj4gQzsKCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBDOyBpKyspIHsKICAgICAgICBpbnQgRWksIEIxLCBCMjsKICAgICAgICBjaW4gPj4gRWkgPj4gQjEgPj4gQjI7CiAgICAgICAgZ1tFaV0ucHVzaF9iYWNrKEIxKTsKICAgICAgICBnW0VpXS5wdXNoX2JhY2soQjIpOwogICAgfQoKICAgIHF1ZXVlPGludD4gcTsKICAgIHEucHVzaCgxKTsKICAgIGRpc3RbMV0gPSAxOwoKICAgIHdoaWxlICghcS5lbXB0eSgpKSB7CiAgICAgICAgaW50IHUgPSBxLmZyb250KCk7IHEucG9wKCk7CiAgICAgICAgZm9yIChpbnQgdiA6IGdbdV0pIHsKICAgICAgICAgICAgZGlzdFt2XSA9IGRpc3RbdV0gKyAxOwogICAgICAgICAgICBxLnB1c2godik7CiAgICAgICAgfQogICAgfQoKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IE47IGkrKykKICAgICAgICBjb3V0IDw8IGRpc3RbaV0gPDwgIlxuIjsKCiAgICByZXR1cm4gMDsKfQo=

NSAyCjMgNSA0CjEgMiAzCg==

5 2
3 5 4
1 2 3