#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--)) #define all(a) a.begin(), a.end() #define ppf pop_front #define ppb pop_back #define pf push_front #define pb push_back #define fr first #define sc second #define ii pair<int, int> #define iii tuple<int, int, int> #define vc vector #define sz(a) a.size() #define mnto(x,y) x = min(x, (__typeof__(x))y) #define mxto(x,y) x = max(x, (__typeof__(x))y) #define setval(arr, x) memset(arr, x, sizeof(arr)) template<typename T> using vv = vc<vc<T>>; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int n, q; void rage() { rep(i, 0, n) cout << -1 << ' '; exit(0); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; int l[q], r[q], a[q]; rep(i, 0, q) cin >> l[i] >> r[i] >> a[i]; vc<int> left(n+5, 0), right(n+5, n-1), add[n+5], rmv[n+5], pp[n], res(n, 0); //left[i] = leftmost possible position for i //right[i] = rightmost possible position for i //add[i] = values whose constraints start at index i //rmv[i] = values whose constraints end before index i //pp[i] = possible positions for i //res[i] = final answer multiset<int> ms; set<int> s; rep(i, 0, q) { mxto(left[a[i]], l[i]); mnto(right[a[i]], r[i]); add[l[i]].pb(a[i]); rmv[r[i]+1].pb(a[i]); } rep(i, 0, n) { if (left[i] > right[i]) rage(); for (auto j : add[i]) ms.insert(j); for (auto j : rmv[i]) ms.erase(ms.find(j)); pp[(sz(ms) ? *ms.rbegin() : 0)].pb(i); } rep(i, 0, n) { for (int j : pp[i]) s.insert(j); auto it = s.lower_bound(left[i]); if (it == s.end() || *it > right[i]) rage(); res[*it] = i; s.erase(it); } rep(i, 0, n) cout << res[i] << ' '; }