Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m;

int s1,t1,s2,t2;

#define MAXN 1500

struct edge

{

	int to,nxt,v;

}e[MAXN * MAXN];

int lin[MAXN] = {0};

int edgenum = 0;

inline void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int d[4][MAXN];

bool v[MAXN];

#define rint register int

inline void SPFA(int s,int t)

{

	queue<int> q;q.push(s);

	memset(d[t],0x3f,sizeof(d[t]));d[t][s] = 0;

	memset(v,false,sizeof(v));

	while(!q.empty())

	{

		rint k = q.front();q.pop();

		v[k] = false;

		for(rint i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[t][e[i].to] > d[t][k] + e[i].v)

			{

				d[t][e[i].to] = d[t][k] + e[i].v;

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return;

}

int tag[2][MAXN][MAXN];

vector< pair<int,int> > g[MAXN];

int ind[MAXN];

int f[MAXN];

inline void toposort()

{

	queue<int> q;

	for(rint i = 1;i <= n;++i)

		if(ind[i] == 0)

			q.push(i);

	while(!q.empty())

	{

		rint k = q.front();q.pop();

		for(register vector< pair<int,int> >::iterator i = g[k].begin();i != g[k].end();++i)

		{

			f[i -> first] = max(f[i -> first],f[k] + i -> second);

			--ind[i -> first];

			if(ind[i -> first] == 0)

			{

				q.push(i -> first);

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	scanf("%d%d%d%d",&s1,&t1,&s2,&t2);

	rint a,b,c;

	for(rint i = 1;i <= m;++i)

	{

		a = read();b = read();c = read();

		add(a,b,c);

	}

	SPFA(s1,0);SPFA(t1,1);

	SPFA(s2,2);SPFA(t2,3);

	memset(tag,0,sizeof(tag));

	for(rint k = 1;k <= n;++k)

	{

		for(rint i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[0][k] + e[i].v + d[1][e[i].to] == d[0][t1])

				tag[0][k][e[i].to] = e[i].v;

			if(d[2][k] + e[i].v + d[3][e[i].to] == d[2][t2])

				tag[1][k][e[i].to] = e[i].v;

		}

	}

	for(rint i = 1;i <= n;++i)

		for(rint j = 1;j <= n;++j)

			if(tag[0][i][j] && tag[1][i][j])

			{

				++ind[j];

				g[i].push_back(make_pair(j,tag[0][i][j]));

			}

	toposort();

	rint ans = 0;

	for(rint i = 1;i <= n;++i)

		ans = max(ans,f[i]);

	memset(ind,0,sizeof(ind));

	for(rint i = 1;i <= n;++i)g[i].clear();

	memset(f,0,sizeof(f));

	for(rint i = 1;i <= n;++i)

		for(rint j = 1;j <= n;++j)

			if(tag[0][i][j] && tag[1][j][i])

			{

				++ind[j];

				g[i].push_back(make_pair(j,tag[0][i][j]));

			}

	toposort();

	for(rint i = 1;i <= n;++i)

		ans = max(ans,f[i]);

	cout << ans << endl;

	return 0;

}