Union-Find アルゴリズムによる解法です。

\(C_1 \leq C_2 \leq \dots \leq C_Q\) を（入力をソートすることで）仮定します。クラスカル法をもとに考えると、以下の手順で答えが求まります。

1. 集合のリスト \(\{1\}, \{2\}, \dots, \{N\}\) を用意し、\(\text{ans} := 0\) と初期化する。
2. \(i = 1, 2, \dots, Q\) の順に以下を行う。
   • \(L_i\) 以上 \(R_i\) 以下の要素をひとつ以上持つ集合をすべて列挙し、そのような集合の個数の \(C_i\) 倍を \(\text{ans}\) に加える。そして、それらの集合をひとつに併合する。
3. すべての集合がひとつに併合されていれば \(\text{ans}\)、されていなければ \(-1\) を出力する。

これは、Union-Find アルゴリズムを用いた上で、各連結成分の最大の頂点番号を保持すると効率的に行えます。時間計算量はソートを含め \(O(Q(\log Q + \alpha(N)))\) です。

実装例（Python）

from atcoder.dsu import DSU

N, Q = map(int, input().split())
CLR = []
for i in range(Q):
    L, R, C = map(int, input().split())
    CLR.append((C, L - 1, R - 1))

d = DSU(N)
r = [i for i in range(N)]
ans = 0
for C, L, R in sorted(CLR):
    p = L
    while p <= R:
        p = r[d.leader(p)]
        ans += C
        if p + 1 <= R:
            nr = r[d.leader(p + 1)]
            d.merge(p, p + 1)
            r[d.leader(p)] = nr
        p += 1
print(ans if d.size(0) == N else -1)