#include<bits/stdc++.h>

using namespace std;

const int N = 5e4 + 50;

const int M = 1e5 + 50;

int fa[N];

int find(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int n, m, root;

struct E
{
    int u;
    int v;
    int w;
}e[M];

bool cmp(const E&a, const E& b)
{
    return a.w < b.w;
}

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

    for(int i = 1; i <= n; i++) 
        fa[i] = i;


    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        e[i] = {u, v, w};
    }

    sort(e + 1, e + m + 1, cmp);

    int res;
    for(int i = 1; i <= m; i++)
    {
        int x = e[i].u;
        int y = e[i].v;

        if(find(x) != find(y))
        {
            fa[find(x)] = find(y);
            res = e[i].w;
        }
    }

    printf("%d", res);

    return 0;
}

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

const int N = 1e4 + 50;

const int M = 2e5 + 50;

const int INF = 0x3f3f3f3f;

int n, m;
int h[N], e[M], w[M], ne[M], idx;

int dist[N], q[N];

bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void spfa()
{
    int hh = 0, tt = 1;
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;

    q[0] = 1;
    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;                   
                }

            }
        }
    }
}

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

    memset(h, -1, sizeof h);

    while(m --)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }

    spfa();

    int res = 0;

    for(int a = 2; a <= n; a++)
    {
        int minw = INF;
        for(int j = h[a]; j != -1; j = ne[j])
        {
            int b = e[j];
            if(dist[a] == dist[b] + w[j])
                minw = min(minw, w[j]);
        }

        res += minw;
    }

    printf("%d", res);

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1050;

const int M = 1e5 + 50;

const int mod = 1e9 + 7;

int n;

int a[N];

int f[N];

vector<int> q[M];

bool st[M];

int main()
{
    for(int i = 1; i < M; i++)
        for(int j = i * 2; j < M; j += i)
        q[j].push_back(i);

    scanf("%d", &n);

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

    f[0] = 1;
    for(int i = 1; i < n; i++)
    {
        memset(st, 0, sizeof st);

        for(int j = i - 1; j >= 0; j--)
        {
            int d = a[i] - a[j], cnt = 0;
            for(auto k : q[d])
            {
                if(!st[k])
                {
                    cnt++;
                    st[k] = true;
                }
            }
            st[d] = true;
            f[i] = (f[i] + (LL)f[j] * cnt) % mod;
        }
    }

    printf("%d", f[n - 1]);
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1e4 + 50;
const int M = 1e5 + 50;

int n, m;
int h[N], e[M], ne[M], idx;

int dfn[N], low[N];

int stk[N], top, ts;

bool in_stk[N];

int res;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ts;
    stk[++top] = u, in_stk[u] = true;

    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j])
        {
            low[u] = min(low[u], dfn[j]);
        }
    }

    if(dfn[u] == low[u])
    {
        int y, cnt = 0;
        do
        {
            y = stk[top --];
            in_stk[y] = false;
            cnt++;
        }while(y != u);

        res += cnt * (cnt - 1) / 2;
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    while(m --)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for(int i = 1; i <= n; i++)
    {
        if(!dfn[i])
            tarjan(i);
    }

    cout << res;

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 150;

int n, m, Q;
char g[N][N];
bool st[N][N];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, char c)
{
    st[x][y] = true;
    g[x][y] = c;
    for(int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 0 && a < m && b >= 0 && b < n && !st[a][b])
        {
            if(g[a][b] == '-' || g[a][b] == '|' || g[a][b] == '+')
                continue;
            dfs(a, b, c); 
        }
    }
}

int main()
{
    cin >> m >> n >> Q;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            g[i][j] = '.';

    while(Q --)
    {
        int op;
        cin >> op;

        if(op == 0)
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            if(x1 > x2) swap(x1, x2);
            if(y1 > y2) swap(y1, y2);

            char c = '-', d = '|';
            if(x1 == x2) swap(c, d);

            for(int i = x1; i <= x2; i++)
                for(int j = y1; j <= y2; j++)
                {
                    auto& t = g[i][j];
                    if(t == d || t == '+') t = '+';
                    else t = c;
                }
        }
        else
        {
            int x, y;
            char c;
            cin >> x >> y >> c;
            memset(st, 0, sizeof st);
            dfs(x, y, c);
        }
     }

     for(int i = n - 1; i >= 0; i--)
     {
        for(int j = 0; j < m; j++)
            cout << g[j][i];

        cout << endl;
    }

    return 0; 
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 50;
const int M = 1e5 + 50;

int h[N];//h[i]存储顶点i的出边编号 

int idx;//出边的编号计数器

int e[M];//存储idx号边的终点

int w[M];//存储idx号边的权值

int ne[M];//存储idx号边的下一条边 

void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[dix] = c;
    h[a] = idx++;
}

include[HTML_REMOVED]

using namespace std;

const int N = 1e5 + 50;
const int M = 1e5 + 50;

int h[N];//h[i]存储顶点i的出边编号

int idx;//出边的编号计数器

int e[M];//存储idx号边的终点

int w[M];//存储idx号边的权值

int ne[M];//存储idx号边的下一条边

void add(int a, int b, int c)
{
e[idx] = b;
ne[idx] = h[a];
w[dix] = c;
h[a] = idx++;
}

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<string> strs;
unordered_map<string, string> vars;

int main()
{
    cin >> n >> m;
    getchar();
    while(n --)
    {
        string str;
        getline(cin, str);
        strs.push_back(str);
    }
    while(m --)
    {
        string key, value;
        cin >> key;
        char c;
        while(c = getchar(), c != '\"');
        while(c = getchar(), c != '\"') value += c;
        vars[key] = value;
    }



    for(auto& str: strs)
    {
        for(int i = 0; i < str.size();)
        {
            if(i + 1 < str.size() && str[i] == '{' && str[i + 1] == '{')
            {
                int j = i + 3;
                string key;
                while(str[j] != ' ' || str[j + 1] != '}' || str[j + 2] != '}')
                    key += str[j++];

                cout << vars[key];
                i = j + 3; 
            }
            else cout << str[i++];

        }
        puts("");

    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 30;

int n;
bool o1[N], o2[N];

string ans[N];

string str;

int main()
{
    string str;
    cin >> str;

    for(int i = 0; i < str.size(); i++)
        if(i + 1 < str.size() && str[i + 1] == ':')
        {
            o2[str[i] - 'a'] = true;
            i++;
        }
        else o1[str[i] - 'a'] = true;

    cin >> n;
    getchar();
    for(int C = 1; C <= n; C++)
    {
        printf("Case %d:", C);
        getline(cin, str);
        stringstream ssin(str);
        vector<string> ops;
        while(ssin >> str) ops.push_back(str);
        for(int i = 0; i < 26; i++) ans[i].clear();
        for(int i = 1; i < ops.size(); i++)
        {
            if(ops[i][0] != '-' || ops[i][1] < 'a' || ops[i].size() != 2) 
                break;
            int k = ops[i][1] - 'a';
            if(o1[k]) ans[k] = "*";
            else if(o2[k] && i + 1 < ops.size()) ans[k] = ops[i + 1], i++;
            else break;
        }

        for(int i = 0; i < 26; i++)
        {
            if(ans[i].size())
            {
                cout << " -" << (char)(i + 'a');
                if(o2[i]) cout << ' ' << ans[i];
            }
        }
        cout << endl;
    }

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

using LL = long long;

using PII = pair<int, int>;

const int N = 250, M = N * N;

int n, m, k, r;
int h[N], e[M], ne[M], idx;
PII p[N];
int dist[N][N];

bool check(PII a, PII b)
{
    LL dx = a.x - b.x;
    LL dy = a.y - b.y;
    return dx * dx + dy * dy <= (LL)r * r;
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs()
{
    queue<PII> q;
    q.push({1, 0});
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = h[t.x]; i != -1; i = ne[i])
        {
            int x = e[i], y = t.y;
            if(x > n) y++;
            if(y <= k)
            {
                if(dist[x][y] > dist[t.x][t.y] + 1)
                {
                    dist[x][y] = dist[t.x][t.y] + 1;
                    q.push({x, y});
                }
            }
        }
    }

    int res = 1e8;
    for(int i = 0; i <= k; i++)
        res = min(res, dist[2][i]);

    return res - 1;
}

int main()
{
    cin >> n >> m >> k >> r;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y;

    for(int i = n + 1; i <= n + m; i++)
        cin >> p[i].x >> p[i].y;

    for(int i = 1; i <= n + m; i++)
        for(int j = i + 1; j <= n + m; j++)
        if(check(p[i], p[j]))
            add(i, j), add(j, i);

    cout << bfs();

    return 0;
}