#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 210;
int k, m, s, e, n;
int g[N][N];
int res[N][N];

void mul(int r[][N], int a[][N], int b[][N])
{
    int temp[N][N];
    memset(temp, 0x3f, sizeof temp);
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
    memcpy(r, temp, sizeof temp);
}

void qmi()
{
    memset(res, 0x3f, sizeof res);
    for (int i = 1; i <= n; i ++) res[i][i] = 0;

    while (k)
    {
        if (k & 1) mul(res, res, g);
        mul(g, g, g);
        k >>= 1;
    }
}

int main()
{
    cin >> k >> m >> s >> e;
    unordered_map<int, int> ids;
    memset(g, 0x3f, sizeof g);
    if (!ids.count(s)) ids[s] = ++ n;
    if (!ids.count(e)) ids[e] = ++ n;
    s = ids[s], e = ids[e];

    while (m --)
    {
        int a, b, c;
        cin >> c >> a >> b;
        if (!ids.count(a)) ids[a] = ++ n;
        if (!ids.count(b)) ids[b] = ++ n;
        a = ids[a], b = ids[b];
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    qmi();

    cout << res[s][e] << endl;

    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 4;

int n, m;

void mul(int c[][N], int a[][N], int b[][N])  // c = a * b
{
    static int t[N][N];
    memset(t, 0, sizeof t);

    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                t[i][j] = (t[i][j] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, t, sizeof t);
}

int main()
{
    cin >> n >> m;

    // {fn, fn+1, sn, pn}
    // pn = n * sn - tn
    int f1[N][N] = {1, 1, 1, 0};
    int a[N][N] = {
        {0, 1, 0, 0},
        {1, 1, 1, 0},
        {0, 0, 1, 1},
        {0, 0, 0, 1},
    };

    int k = n - 1;

    // 快速幂
    while (k)
    {
        if (k & 1) mul(f1, f1, a);  // f1 = f1 * a
        mul(a, a, a);  // a = a * a
        k >>= 1;
    }

    cout << (((LL)n * f1[0][2] - f1[0][3]) % m + m) % m << endl;

    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 3;

int n, m;

void mul(int c[], int a[], int b[][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;

    memcpy(c, temp, sizeof temp);
}

void mul(int c[][N], int a[][N], int b[][N])
{
    int temp[N][N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, temp, sizeof temp);
}

int main()
{
    cin >> n >> m;

    int f1[N] = {1, 1, 1};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };

    n -- ;
    while (n)
    {
        if (n & 1) mul(f1, f1, a);  // res = res * a
        mul(a, a, a);  // a = a * a
        n >>= 1;
    }

    cout << f1[2] << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 110, M = 2510;

int n, m, K;
LL d[N][N], f[N][N];

struct Edge
{
    int a, b, c;
}edge[M];

void mul(LL c[][N], LL a[][N], LL b[][N])
{
    static LL t[N][N];
    memset(t, 0x3f, sizeof t);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            for (int k = 1; k <= n; k ++ )
                t[i][j] = min(t[i][j], a[i][k] + b[k][j]);
    memcpy(c, t, sizeof t);
}

LL qmi()
{
    while (K)
    {
        if (K & 1) mul(d, d, f);
        mul(f, f, f);
        K >>= 1;
    }
    return d[1][n];
}

int main()
{
    scanf("%d%d%d", &n, &m, &K);
    memset(d, 0x3f, sizeof d);
    for (int i = 1; i <= n; i ++ ) d[i][i] = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = c;
        edge[i] = {a, b, c};
    }

    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    memcpy(f, d, sizeof f);
    for (int k = 0; k < m; k ++ )
    {
        int a = edge[k].a, b = edge[k].b, c = edge[k].c;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                f[i][j] = min(f[i][j], d[i][a] - c + d[b][j]);
    }

    printf("%lld\n", qmi());
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) x&(-x)
const int N=2e5;
ll c1[N],c2[N],n,m,a[N];
ll add(ll x,ll y){
    for(ll i=x;i<=n;i+=lowbit(i)){
        c1[i]+=y;
        c2[i]+=x*y;
    }
}
ll ask(ll x){
    ll ans=0;
    for(ll i=x;i;i-=lowbit(i)) ans+=(x+1)*c1[i]-c2[i];
    return ans;
}
int main(){
    scanf("%lld%lld\n",&n,&m);
    for(ll i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        add(i,a[i]-a[i-1]);
    }
    getchar();
    while(m--){
        char ch=getchar();
        if(ch=='Q'){
            ll x,y;
            scanf("%lld%lld\n",&x,&y);
            cout<<ask(y)-ask(x-1)<<endl;
        }
        if(ch=='C'){
            ll x,y,d;
            scanf("%lld%lld%lld\n",&x,&y,&d);
            add(x,d);
            add(y+1,-d);
        }
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;

int m, p;
struct Node
{
    int l, r;
    int v;  // 区间[l, r]中的最大值
}tr[N * 4];

void pushup(int u)  // 由子节点的信息，来计算父节点的信息
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;   // 树中节点，已经被完全包含在[l, r]中了

    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));

    return v;
}

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}


int main()
{
    int n = 0, last = 0;
    scanf("%d%d", &m, &p);
    build(1, 1, m);

    int x;
    char op[2];
    while (m -- )
    {
        scanf("%s%d", op, &x);
        if (*op == 'Q')
        {
            last = query(1, n - x + 1, n);
            printf("%d\n", last);
        }
        else
        {
            modify(1, n + 1, ((LL)last + x) % p);
            n ++ ;
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;

int n, m;
int w[N];

struct Node
{
    int l, r;
    LL dt, mn;
}tr[N * 4];

void pushup(int u)
{
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
}

void pushdown(int u)
{
    auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    l.dt += root.dt, l.mn += root.dt;
    r.dt += root.dt, r.mn += root.dt;
    root.dt = 0;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void update(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].dt += d, tr[u].mn += d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].mn;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = 1e18;
        if (l <= mid) res = min(res, query(u << 1, l, r));
        if (r > mid) res = min(res, query(u << 1 | 1, l, r));
        return res;
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);

    build(1, 0, n - 1);

    scanf("%d", &m);
    while (m -- )
    {
        int l, r;
        char c;
        scanf("%d %d%c", &l, &r, &c);
        if (c == '\n')
        {
            if (l <= r) printf("%lld\n", query(1, l, r));
            else printf("%lld\n", min(query(1, 0, r), query(1, l, n - 1)));
        }
        else
        {
            int d;
            scanf("%d", &d);
            if (l <= r) update(1, l, r, d);
            else update(1, 0, r, d), update(1, l, n - 1, d);
        }
    }

    return 0;
}

#include<iostream>

using namespace std;

const int N=1e5+10;
int tree[N];
int n,m;

int lowbit(int x){
    return x&(-x);
}

void add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)){
        tree[i]+=c;
    }
}

int query(int x){
    int sum=0;
    for(int i=x;i;i-=lowbit(i)){
        sum+=tree[i];
    }
    return sum;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        add(i,x),add(i+1,-x);
    }
    while(m--){
        char op[2];
        scanf("%s",&op);
        if(op[0]=='C'){
            int l,r,c;
            scanf("%d%d%d",&l,&r,&c);
            add(l,c),add(r+1,-c);
        }else{
            int x;
            scanf("%d",&x);
            printf("%d\n",query(x));
        }
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int a[N];
int tr[N];
int Greater[N], lower[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ )
    {
        int y = a[i];
        Greater[i] = sum(n) - sum(y);
        lower[i] = sum(y - 1);
        add(y, 1);
    }

    memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;
    for (int i = n; i; i -- )
    {
        int y = a[i];
        res1 += Greater[i] * (LL)(sum(n) - sum(y));
        res2 += lower[i] * (LL)(sum(y - 1));
        add(y, 1);
    }

    printf("%lld %lld\n", res1, res2);

    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll; // 本题中 a 的上线是 10 ^ 9，故答案可能会超过 int 的上限
const int N = 100005;
int n, a[N], diff[N], sz; // 离散化
// 树状数组
ll fw[N], res;
inline void add(int x, const ll c) {
    for (; x <= sz; x += x & -x) fw[x] = max(fw[x], c);
}
inline ll qry(int x) {
    ll res = 0;
    for (; x; x &= x - 1) res = max(res, fw[x]);
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        diff[i - 1] = a[i];
    }
    sort(diff, diff + n);
    sz = unique(diff, diff + n) - diff;
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(diff, diff + sz, a[i]) - diff + 1; // 求出离散化之后的值
        ll f = diff[a[i] - 1] + qry(a[i] - 1); // 求出 f[i]。
        res = max(res, f), add(a[i], f);       // 更新答案并将 f[i] 存到树状数组中 a[i] 的位置。
    }
    printf("%lld\n", res);
    return 0;
}