申请加强数据

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+10;
const int INF=0x3f3f3f3f;
struct Edge{
	int to,next,val;
}edge[N<<1];
int head[N],dis[N];
int n,m,cnt;
void add(int u,int v,int w){
	edge[++cnt].to=v;
	edge[cnt].val=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void dijkstra(){
	fill(dis+1,dis+1+n,INF);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<> > qu;
	dis[1]=0;
	qu.push({0,1});
	while(!qu.empty()){
		int u=qu.top().second,d=qu.top().first;
		qu.pop();
		if(d>dis[u]) continue;
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].to,w=edge[i].val;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				qu.push({dis[v],v});
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	memset(head,0,sizeof(head));
	for(int i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dijkstra();
	for(int i=1;i<=n;i++){
		if(dis[i]==INF) cout<<-1<<' ';
		else cout<<dis[i]<<' ';
	}
	return 0;
}