Sgu/185

/by Logic
#include<stdio.h>
const int maxn=405,max=100000;
int n,m,l[maxn][maxn]={0},f[maxn][maxn]={0},as[maxn],adj[maxn][maxn];
int len,p[maxn][2],z[maxn][maxn]={0},zz=1;
int dijk()
{
	int i,j,dis[maxn],vis[maxn]={0},min,cur;
	dis[1]=0;
	for(i=2;i<=n;dis[i++]=max);
	for(i=1;i<=n;i++)
		{
		min=max;
		for(j=1;j<=n;j++)
			if(!vis[j]&&dis[j]<min) {min=dis[j];cur=j;}
		for(j=0;j<as[cur];j++)
			if(dis[cur]+l[cur][adj[cur][j]]<dis[adj[cur][j]])
				dis[adj[cur][j]]=dis[cur]+l[cur][adj[cur][j]];
		vis[cur]=1;
		}
	return dis[n];
}
void SPFA(int x)
{
	int i,j,qu[maxn*10],dis[maxn],vis[maxn]={0},cur,en=1;
	for(i=1;i<=n;dis[i++]=max);
	qu[0]=1;dis[1]=0;
	for(i=0;i<en;i++)
		{
		cur=qu[i];
		vis[cur]=0;
		for(j=0;j<as[cur];j++)
			if(f[cur][adj[cur][j]]>0&&dis[cur]+l[cur][adj[cur][j]]<dis[adj[cur][j]])
				{
				dis[adj[cur][j]]=dis[cur]+l[cur][adj[cur][j]];
				p[adj[cur][j]][x]=cur;
				if(!vis[adj[cur][j]])
					{vis[adj[cur][j]]=1;qu[en++]=adj[cur][j];}
				}
		}
	for(i=n;i>0;i=p[i][x])
		{
		f[i][p[i][x]]++;
		f[p[i][x]][i]--;
		if(l[p[i][x]][i]<0) {z[p[i][x]][i]=1;z[i][p[i][x]]=1;}
		l[i][p[i][x]]=0-l[p[i][x]][i];
		}
	if(dis[n]>len) zz=0;
}
void pri(int cur,int x)
{
	if(cur!=1)
		{
		if(z[p[cur][x]][cur]) x=(x+1)%2;
		pri(p[cur][x],x);
		}
	printf("%d",cur);
	if(cur!=n) printf(" ");
}
int main()
{
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	int i,x,y,z;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
		{
		scanf("%d%d%d",&x,&y,&z);
		l[x][y]=z;
		l[y][x]=z;
		f[x][y]=1;
		f[y][x]=1;
		adj[x][as[x]++]=y;
		adj[y][as[y]++]=x;
		}
	len=dijk();
	for(i=0;i<2;i++)
		SPFA(i);
	//for(i=1;i<=n;i++) printf("%d %d\n",p[i][0],p[i][1]);
	if(zz)
		{
		for(i=0;i<2;i++)
			{
			pri(n,i);
			printf("\n");
			}
		}
	else printf("No solution\n");
	return 0;
}