#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; #define fi first #define se second #define all(x) x.begin(), x.end() #define sz(x) (int)(x.size()) #define MASK(i) (1ll << i) const int N = 1e5 + 5; int n, q, res[N]; bool b[N], f[N]; struct Qe { int l, r, x; }qry[N]; namespace sub1 { bool check() { return (n <= 10); } void solve() { vector<int> v(n); for (int i = 0; i < n; i++) v[i] = i; do { bool check = true; for (int i = 1; i <= q; i++) { int l = qry[i].l, r = qry[i].r, x = qry[i].x; int mi = (int)1e9; for (int j = l - 1; j < r; j++) { mi = min(mi, v[j]); } if (mi != x) { check = false; break; } } if (check) { for (int i = 0; i < n; i++) cout << v[i] << " \n"[i == n - 1]; return; } } while (next_permutation(all(v))); for (int i = 1; i <= n; i++) cout << -1 << " \n"[i == n]; } } namespace sub2 { bool check() { return (n <= 1000 && q <= 1000); } bool b[N], f[N]; void solve() { sort(qry + 1, qry + q + 1, [](Qe a, Qe b) { return a.x > b.x; }); vector<Qe> v; for (int i = 1; i <= q; i++) { int l = qry[i].l, r = qry[i].r, x = qry[i].x; int cur = sz(v); int k = l, h = l; while (k <= r) { while (b[k]) k++; h = max(h, k); while (h <= r && !b[h]) h++; v.push_back({k, h - 1, x}); k = h; } if (sz(v) == cur) { for (int i = 1; i <= n; i++) cout << -1 << " \n"[i == n]; return; } for (int j = l; j <= r; j++) b[j] = true; } for (int i = 1; i <= n; i++) res[i] = -1; for (int i = 0; i < sz(v); i++) { int l = v[i].l, r = v[i].r, x = v[i].x; for (int j = l; j <= r; j++) res[j] = x; f[x] = true; } vector<int> c; for (int i = 0; i < n; i++) { if (!f[i]) { c.push_back(i); } f[i] = false; } int id = 0; for (int i = 1; i <= n; i++) { if (res[i] == -1 && id < sz(c)) res[i] = c[id++]; } for (int i = 1; i <= n; i++) { if (f[res[i]] == true) { if (id < sz(c) && c[id] > res[i]) res[i] = c[id++]; else { for (int i = 1; i <= n; i++) cout << -1 << " \n"[i == n]; return; } } f[res[i]] = true; } for (int i = 1; i <= n; i++) cout << res[i] << " \n"[i == n]; } } namespace sub3 { int lab[N], mx[N]; void make_set() { for (int i = 1; i <= n; i++) lab[i] = -1, mx[i] = i; } int find_(int u) { return lab[u] < 0 ? u : lab[u] = find_(lab[u]); } void unite(int a, int b) { a = find_(a), b = find_(b); if (a == b) return; if (lab[a] > lab[b]) swap(a, b); mx[a] = max(mx[a], mx[b]); lab[a] += lab[b]; lab[b] = a; } bool f[N]; void solve() { sort(qry + 1, qry + q + 1, [](Qe a, Qe b) { return a.x > b.x; }); vector<Qe> v; make_set(); for (int i = 1; i <= q; i++) { int l = qry[i].l, r = qry[i].r, x = qry[i].x; int cur = sz(v); int k = l, h = l; while (k <= r) { int par = find_(k); if (mx[par] != k) k = mx[par] + 1; h = max(h, k); if (h > r) break; while (h <= r) { int par = find_(h); if (h - 1 >= l) unite(h, h - 1); if (mx[par] == h) h++; else break; } v.push_back({k, h - 1, x}); k = h; } // if (cur == sz(v)) { // for (int i = 1; i <= n; i++) cout << -1 << " \n"[i == n]; // return; // } } for (int i = 1; i <= n; i++) res[i] = -1; for (int i = 0; i < sz(v); i++) { int l = v[i].l, r = v[i].r, x = v[i].x; for (int j = l; j <= r; j++) res[j] = x; f[x] = true; } vector<int> c; for (int i = 0; i < n; i++) { if (!f[i]) { c.push_back(i); } f[i] = false; } int id = 0; for (int i = 1; i <= n; i++) { if (res[i] == -1 && id < sz(c)) res[i] = c[id++]; } for (int i = 1; i <= n; i++) { if (f[res[i]] == true) { if (id < sz(c) && c[id] > res[i]) res[i] = c[id++]; else { for (int i = 1; i <= n; i++) cout << -1 << " \n"[i == n]; return; } // res[i] = c[id++]; } f[res[i]] = true; } for (int i = 1; i <= n; i++) cout << res[i] << " \n"[i == n]; } } void solve() { cin >> n >> q; for (int i = 1; i <= q; i++) { int l, r, val; cin >> l >> r >> val; l++, r++; qry[i] = {l, r, val}; } // sub1::solve(); // sub2::solve(); sub3::solve(); return; if (sub1::check()) { sub1::solve(); return; } else if (sub2::check()) { sub2::solve(); return; } else { sub3::solve(); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // #define TASK "chonqua" // freopen(TASK".inp", "r", stdin); // freopen(TASK".out", "w", stdout); int T = 1; // cin >> T; while (T--) { solve(); } }