int mp[n][n];
int n,m;
int dis[n];
int vis[n];
void init()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
mp[i][j]=0;
else
mp[i][j]=INF;
}
}
}
int spfa(int st,int ed)
{
for(int i=1;i<=n;i++)
{
dis[i]=INF;
vis[i]=0;
}
dis[st]=0;
queue<int>q;
q.push(st);
vis[st]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=1;i<=n;i++)
{
if(dis[i]>dis[now]+mp[now][i])
{
dis[i]=dis[now]+mp[now][i];
if(vis[i]==0)
{
q.push(i);
vis[i]=1;
}
}
}
}
return dis[ed];
}
int n,m;
int dis[n];
int vis[n];
void init()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
mp[i][j]=0;
else
mp[i][j]=INF;
}
}
}
int spfa(int st,int ed)
{
for(int i=1;i<=n;i++)
{
dis[i]=INF;
vis[i]=0;
}
dis[st]=0;
queue<int>q;
q.push(st);
vis[st]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=1;i<=n;i++)
{
if(dis[i]>dis[now]+mp[now][i])
{
dis[i]=dis[now]+mp[now][i];
if(vis[i]==0)
{
q.push(i);
vis[i]=1;
}
}
}
}
return dis[ed];
}