- #include < cstdio > #include < cstring > #include < algorithm > using namespace std;
- char buf[10000000],
- *ptr = buf - 1;
- inline int readint() {
- int f = 1,
- n = 0;
- char ch = *++ptr;
- while (ch < ‘0‘ || ch > ‘9‘) {
- if (ch == ‘ - ‘) f = -1;
- ch = *++ptr;
- }
- while (ch <= ‘9‘ && ch >= ‘0‘) {
- n = (n << 1) + (n << 3) + ch - ‘0‘;
- ch = *++ptr;
- }
- return f * n;
- }
- const int maxn = 1000 + 10;
- struct Matrix {
- int n,
- m,
- num[110][110];
- Matrix() {}
- Matrix(int _n, int _m) {
- n = _n;
- m = _m;
- memset(num, 0x3f, sizeof(num));
- }
- Matrix operator * (const Matrix & a) {
- Matrix b(n, a.m);
- for (int i = 1; i <= n; i++) for (int j = 1; j <= b.m; j++) for (int k = 1; k <= m; k++) b.num[i][j] = min(b.num[i][j], num[i][k] + a.num[k][j]);
- return b;
- }
- };
- Matrix ksm(Matrix a, int b) {
- Matrix s = a;
- b--;
- while (b) {
- if (b & 1) s = s * a;
- b >>= 1;
- a = a * a;
- }
- return s;
- }
- int N,
- T,
- S,
- E;
- int w[maxn],
- u[maxn],
- v[maxn];
- int num[maxn * 2],
- cnt = 0;
- int main() {
- fread(buf, sizeof(char), sizeof(buf), stdin);
- N = readint();
- T = readint();
- S = readint();
- E = readint();
- num[++cnt] = S;
- num[++cnt] = E;
- for (int i = 1; i <= T; i++) {
- w[i] = readint();
- num[++cnt] = u[i] = readint();
- num[++cnt] = v[i] = readint();
- }
- sort(num + 1, num + cnt + 1);
- cnt = unique(num + 1, num + cnt + 1) - (num + 1);
- S = lower_bound(num + 1, num + cnt + 1, S) - num;
- E = lower_bound(num + 1, num + cnt + 1, E) - num;
- for (int i = 1; i <= T; i++) {
- u[i] = lower_bound(num + 1, num + cnt + 1, u[i]) - num;
- v[i] = lower_bound(num + 1, num + cnt + 1, v[i]) - num;
- }
- Matrix ans(cnt, cnt);
- for (int i = 1; i <= T; i++) ans.num[u[i]][v[i]] = ans.num[v[i]][u[i]] = w[i];
- ans = ksm(ans, N);
- printf("%d\n", ans.num[S][E]);
- return 0;
- }