#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
    int n, m;
    cin >> n >> m;
    vector<vi> d(n, vi(n));
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        d[a][b] = d[b][a] = 1;
    }
    vi dp(1<<n, INF);
    dp[0] = 0;
    rep(i, n) dp[1<<i] = 1;
    rep(mask, 1<< n) if(dp[mask] != INF) {
        rep(i, n) {
            if(mask & (1<<i)) continue;
            bool f = true;
            rep(j, n) if(mask & (1<<j)) {
                f &= d[i][j];
            }
            if(f) dp[mask | (1<<i)] = 1;
        }
    }
    rep(mask, 1<<n) {
        for(int maskA = mask; maskA != 0; maskA = mask&(maskA-1)) {
            int maskB = mask - maskA;
            dp[mask] = min(dp[mask], dp[maskA] + dp[maskB]);
        }
    }
    cout << dp[(1<<n)-1] << '\n';
    return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 2e5+8, inf  = 1e18+9, mod  = 998244353;

struct edge { int v, w; };
int n, m, ans[maxn], vs[maxn];
vector<edge> G[maxn];

void dfs(int u, int p) {
    for (auto [v, w] : G[u]) if (v != p && !vs[v]) {
        if (w == ans[u]) ans[v] = (w % n) + 1; else ans[v] = w;
        vs[v] = 1; dfs(v, u);
    }
}

void solve() {
    int i, j, u, v, w;
    cin >> n >> m;
    for (i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    ans[1] = 1; vs[1] = 1;
    dfs(1, -1);
    for (i = 1; i <= n; i++) cout << ans[i] << endl;
}

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); //cout << fixed << setprecision(15);
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

