#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
#define m1 (1<<n)-1
using namespace std;

const int N=20;		//最大层数  
const int M=5e5;	//最大点数 
const int mod=998244353;
vector<pair<int,int> > g[M];	//原图 
vector<pair<int,int> > h[M];	//反向建的图 
int n,m;
int include13=0;	//最终答案
priority_queue<pair<int,int> > q;//优先队列  第一个数存负的点权 第二个数存点的编号  
int gans[M],hans[M],run[M];	//run 是表示是否是本轮次考虑的点  
int gans2[M],hans2[M];
void init(int u,int now){
	if(u>m1)	return;
	gans[u]=1e18,hans[u]=1e18;
	gans2[u]=1,hans2[u]=1; 
	run[u]=now;
	init(u*2,now),init(u*2+1,now);
} 
int gdfs(int u){
	if(u>m1)	return 0;
	return (gdfs(u*2)+gdfs(u*2+1)+(gans[u]!=1e18))%mod;
}
int hdfs(int u){
	if(u>m1)	return 0;
	return (hdfs(u*2)+hdfs(u*2+1)+(hans[u]!=1e18))%mod;
}
int gdfs2(int u){
	if(u>m1)	return 0;
	int ret=(gdfs2(u*2)+gdfs2(u*2+1))%mod;
	if(gans[u]!=1e18)	ret+=gans[u];
	ret%=mod;
	return ret;
}
int hdfs2(int u){
	if(u>m1)	return 0;
	int ret=(hdfs2(u*2)+hdfs2(u*2+1))%mod;
	if(hans[u]!=1e18)	ret+=hans[u];
	ret%=mod;
	return ret;
}
inline void dfs(int u){
	if(u>m1)	return;
	init(u,u);
//	cout<<hans[3]<<endl;
	int now=u;
	while(now){
		run[now]=u;
		gans[now]=1e18,hans[now]=1e18;
		gans2[now]=u,hans[now]=u; 
		now>>=1;
	}
	gans[u]=hans[u]=0;
	q.push(mp(0,u));
	int a1=0,a2=0;
	while(!q.empty()){
		int u1=q.top().second;
		int u1_=-q.top().first;
//		cout<<u1<<' '<<u1_<<endl;
		q.pop();
//		cout<<u1<<' '<<u1_<<endl;
		
		if(!gans2[u1])	continue;
		a1++;
		gans2[u1]=0;
		for(int i=0;i<g[u1].size();i++){
			int v1=g[u1][i].first;
			int w1=g[u1][i].second;
			if(gans[v1]>gans[u1]+w1&&run[v1]==u){
				gans[v1]=gans[u1]+w1;
				q.push(mp(-gans[v1],v1));
			}
		} 
	}
	q.push(mp(0,u));
	while(!q.empty()){
		int u1=q.top().second;
		int u1_=-q.top().first;
//		cout<<u1<<' '<<u1_<<endl;
		q.pop();
		if(!hans2[u1])	continue;
		a2++; 
		hans2[u1]=0;
		for(int i=0;i<h[u1].size();i++){
			int v1=h[u1][i].first;
			int w1=h[u1][i].second;
			if(hans[v1]>hans[u1]+w1&&run[v1]==u){
//				cout<<'#'<<' '<<v1<<' '<<w1<<endl;
				hans[v1]=hans[u1]+w1;
				q.push(mp(-hans[v1],v1));
			}
		} 
	}
//	for(int i=1;i<=m1;i++){
//		cout<<gans[i]<<' ';
//	}
//	cout<<endl;
//	for(int i=1;i<=m1;i++){
//		cout<<hans[i]<<' ';
//	}
//	cout<<endl;
	int g_l=gdfs(u*2)+1;
	int g_l1=gdfs2(u*2);
	int g_r=gdfs(u*2+1)+1;
	int g_r1=gdfs2(u*2+1);
	int h_l=hdfs(u*2)+1;
	int h_l1=hdfs2(u*2);
	int h_r=hdfs(u*2+1)+1;
	int h_r1=hdfs2(u*2+1);
//	cout<<g_l<<' '<<g_l1<<' '<<g_r<<' '<<g_r1<<' '<<h_l<<' '<<h_l1<<' '<<h_r<<' '<<h_r1<<endl;
	include13+=g_l*h_r1;
	include13+=h_r*g_l1;
	include13+=g_r*h_l1;
	include13+=h_l*g_r1;
	include13%=mod;
//	cout<<"pt"<<' '<<u<<endl;
//	cout<<a1<<' '<<a2<<endl;
//	for(int i=1;i<=m1;i++){
//		cout<<run[i]<<' ';
//	}
//	cout<<endl;
//	for(int i=1;i<=m1;i++){
//		cout<<gans[i]<<' ';
//	}
//	cout<<endl;
//	for(int i=1;i<=m1;i++){
//		cout<<hans[i]<<' ';
//	}
//	cout<<endl;
//	cout<<endl;
	dfs(u*2),dfs(u*2+1);
	return;
} 
signed main(){
//	freopen("trade.in","r",stdin);
//	freopen("trade.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=2;i<=m1;i++){
		int u=i;
		int v=i/2;
		int w;
		cin>>w;
		g[u].push_back(mp(v,w));
		h[v].push_back(mp(u,w));
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		g[u].push_back(mp(v,w));
		h[v].push_back(mp(u,w)); 
	}
	dfs(1);
	printf("%lld\n",include13);
	return 0;
} 

提交记录