#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include "../../../cp/lib/debug.hpp"
#else
#define debug(...)
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);
	ll n, c;
	cin >> n >> c;
	multiset<pair<ll, ll>> st;
	for (int i = 0; i < n; i++) {
		int a, b, x;
		cin >> a >> b >> x;
		st.insert({a, x});
		st.insert({b + 1, -x});
	}
	ll cur = 0, ans = 0, prev = -1;
	for (auto&& [x, y] : st) {
		if (prev != -1) ans += min(cur, c) * (x - prev);
		cur += y;
		debug(x, y, cur, ans);
		prev = x;
	}
	cout << ans << '\n';
}

#include <bits/stdc++.h>
using namespace std;
const int N=1050;
const int INF=0x3f3f3f3f;
// dp[i][j]表示点i到点j的最短回文串路径
int dp[N][N];
int n,m,u,v;
char c[2];
vector<int> g[N][30];
int main(){
//    freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    queue<pair<int,int>> q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=INF;
        }
    }
    for(int i=1;i<=n;i++){
        dp[i][i]=0;
        q.push({i,i});
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d %s",&u,&v,c);
        int w=c[0]-'a';
        g[u][w].push_back(v);
        g[v][w].push_back(u);
        if(u!=v){
            // important
            dp[u][v]=1;
            dp[v][u]=1;
            q.push({u,v});
        }
    }
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        int tu=t.first;
        int tv=t.second;
        for(int i=0;i<26;i++){
            if(!g[tu][i].empty() && !g[tv][i].empty()){
                // 可以向两边拓展这个字符
                for(int j=0,us=g[tu][i].size();j<us;j++){
                    for(int k=0,ts=g[tv][i].size();k<ts;k++){
                        int ttu=g[tu][i][j];
                        int ttv=g[tv][i][k];
                        if(dp[ttu][ttv]>dp[tu][tv]+2){
                            dp[ttu][ttv]=dp[tu][tv]+2;
                            dp[ttv][ttu]=dp[tu][tv]+2;
                            q.push({ttu,ttv});
                        }
                    }
                }
            }
        }
    }
    printf("%d\n",dp[1][n]==INF?-1:dp[1][n]);
    return 0;
}