只A了最后一个测试点，参照了题解也没找出来···

#include <bits/stdc++.h>
using namespace std;
const int N=2000005;
const int mod=100003;
long long n,m,dis[N],last[N],cnt[N];
bool mark[N];
struct qwe{
	int x,y,next;
};qwe e[N];
struct awa{
	int op;
	long long dis;
	awa(int op_,long long dis_){
		op=op_;
		dis=dis_;
	}
};
priority_queue<awa> pq;
bool operator <(awa a,awa b){
	return a.dis>b.dis;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1,j=1; i<=m; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e[j].x=x;
		e[j].y=y;
		e[j].next=last[x];
		last[x]=j;
		j++;
		e[j].x=y;
		e[j].y=x;
		e[j].next=last[x];
		last[x]=j;
		j++;
	}
	for(int i=1; i<=n; i++){
		dis[i]=1e20;
		mark[i]=0;
	}
	pq.push(awa(1,0));
	dis[1]=0;
	cnt[1]=1;
	while(!pq.empty()){
		int kl=pq.top().op;				
		pq.pop();
		if(mark[kl]==1){
			continue;
		}
		mark[kl]=1;
		for(int i=last[kl]; i; i=e[i].next){
			int g=e[i].y;			
			if(dis[g]==dis[kl]+e[i].x){
				cnt[g]=(cnt[g]+cnt[kl])%mod;
			}
			if(dis[g]>dis[kl]+e[i].x){
				dis[g]=dis[kl]+e[i].x;
				cnt[g]=cnt[kl];
				pq.push(awa(g,dis[g]));
			}
		}
	}
	for(int i=1; i<=n; i++){
		cout<<cnt[i]<<endl;
	}
	return 0;
}