Cod sursa(job #805315)
#include<cstdio>
#define INF 0x3f3f3f3f
#define maxn 50005
#define maxm 250005
using namespace std;
struct graf {int x,y,c;} G[maxm];
int d[maxn],n,m,i,ok;
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=2;i<=n;++i)
d[i]=INF;
for(i=1;i<=m;++i)
{
scanf("%d%d%d",&G[i].x,&G[i].y,&G[i].c);
if(G[i].x==1)
d[G[i].y]=G[i].c;
}
do
{
ok=0;
for(i=1;i<=m;++i)
if(d[G[i].y]>d[G[i].x]+G[i].c)
{
d[G[i].y]=d[G[i].x]+G[i].c;
ok=1;
}
}
while (ok);
for(i=2;i<=n;++i)
if(d[i]!=INF)
printf("%d ",d[i]);
else
printf("0 ");
printf("\n");
return 0;
}