#include <bits/stdc++.h>
#define P pair<int, int> //pair<距离，编号>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 100005;
int m, n, u, v, w, st, ed1, ed2;
struct node
{
    int v, w, link;
} edge[2 * maxn];
int dis[maxn], head[maxn], cnt = 0;
priority_queue<P, vector<P>, greater<P>> q; //最小的元素在队首
void add_edge(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].link = head[u];
    head[u] = cnt++;
}
void Dijkstra(int n, int s)
{
    int visit[maxn];
    for (int i = 1; i <= n; i++)
    {
        dis[i] = inf;
        visit[i] = 0;
    }
    dis[s] = 0;
    q.push(make_pair(0, s));
    while (q.size())
    {
        int u = q.top().second;
        q.pop();
        if (visit[u] == 0)
        {
            visit[u] = 1;
            for (int i = head[u]; i != -1; i = edge[i].link)
            {
                int v = edge[i].v;
                if (dis[v] > dis[u] + edge[i].w)
                {
                    dis[v] = dis[u] + edge[i].w;
                    q.push(make_pair(dis[v], v));
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    cin >> st >> ed1 >> ed2;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    Dijkstra(n, st);
    int x = min(dis[ed1], dis[ed2]);
    Dijkstra(n, ed1);
    int y = dis[ed2];
    if (x != inf)
        cout << x + y;
    else
        cout << -1;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int pre[100005];//并查集
int n,m;
int find(int x) //查找根节点
{
    int r = x;
    while (pre[r] != r) //返回根节点 r
        r = pre[r];

    int i = x, j;
    while (i != r) //路径压缩
    {
        j = pre[i]; // 在改变上级之前用临时变量  j 记录下他的值
        pre[i] = r; //把上级改为根节点
        i = j;
    }
    return r;
}
void join(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
        pre[fx] = fy;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        pre[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int op,u,v;
        cin>>op>>u>>v;
        if (op == 1)
        {
            join(u,v);
        }
        else if (op == 2)
        {
            int x=find(u);
            int y=find(v);
            if (x==y&&x&&y)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define NUM 30005
int S[NUM], n, m;
struct Edge
{
    int t, u, v, w;
} edge[50005];
int cmp(const void *a, const void *b) { return (*(struct Edge *)a).w > (*(struct Edge *)b).w ? 1 : -1; }
int find_set(int u)
{
    if (u != S[u])
        S[u] = find_set(S[u]);
    return S[u];
}
void kruskal()
{
    long long sum = 0,ct = 0;
    for (int i = 1; i <= n; i++) S[i] = i;
    qsort(edge + 1, m, sizeof(edge[1]), cmp);
    for (int i = 1; i <= m; i++)
    {
        int b = find_set(edge[i].u);
        int c = find_set(edge[i].v);
        if (b == c) continue;
        S[c] = b;
        sum += edge[i].w;
    }
    printf("%lld\n", sum);
    // for (register int i = 1; i <= ct; i++) printf("%d ", ans[i]);
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) scanf("%d%d%d",&edge[i].u, &edge[i].v, &edge[i].w);
    kruskal();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;//点数最大值
int n, m, cnt;//n个点，m条边
struct Edge
{
    int to, w, next;//终点，边权，同起点的上一条边的编号
}edge[maxn];//边集
int head[maxn];//head[i],表示以i为起点的第一条边在边集数组的位置（编号）
void init()//初始化
{
    for (int i = 0; i <= n; i++) head[i] = -1;
    cnt = 0;
}
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
    edge[cnt].to = v; //终点
    edge[cnt].w = w; //权值
    edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++;//更新以u为起点上一条边的编号
}
int main()
{
    cin >> n >> m;
    int u, v, w;
    init();//初始化
    for (int i = 1; i <= m; i++)//输入m条边
    {
        cin >> u >> v >> w;
        add_edge(u, v, w);//加边
        /*
        加双向边
        add_edge(u, v, w);
        add_edge(v, u, w);
        */
    }
    for (int i = 1; i <= n; i++)//n个起点
    {
        cout << i << endl;
        for (int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边
        {
            cout << i << " " << edge[j].to << " " << edge[j].w << endl;
        }
        cout << endl;
    }
    return 0;
}

//链式向前星
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, m, cnt;
struct Edge
{
    int to, next;
} edge[4 * maxn];
int head[maxn]; //head[i],表示以i为起点的第一条边在边集数组的位置（编号）
int visit[maxn];
void init() //初始化
{
    for (int i = 0; i <= n; i++)
        head[i] = -1;
    cnt = 0;
}
void add_edge(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
    visit[v]++;
}
priority_queue<int> que;
int main()
{
    cin >> n >> m;
    int u, v, ch = n;
    init();
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        add_edge(u, v);
    }
    for (int i = 1; i <= n; i++)
    {
        if (visit[i] == 0)
            que.push(i);
    }
    while (!que.empty())
    {
        int res = que.top();
        que.pop();
        cout << res<<" ";
        for (int j = head[res]; j != -1; j = edge[j].next)
        {
            visit[edge[j].to]--;
            if(!visit[edge[j].to])
                que.push(edge[j].to);
        }
    }
    return 0;
}