#include <iostream>

const int MAX=1002;
const int DIST=800;
const int INF=0x7FFFFFFF;

using namespace std;

int N,T,A;
int S[MAX],F[MAX],G[MAX],C[MAX],H[MAX],Ans[MAX];

void init()
{
	int i;
	freopen("tan.in","r",stdin);
	freopen("tan.out","w",stdout);
	scanf("%d%d",&T,&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d",&S[i],&C[i]);
	}
	S[0]=C[0]=C[N+1]=0;
	S[N+1]=T;
}

void dynamic1()
{
	int i,j;
	F[0]=G[0]=0;
	for (i=1;i<=N+1;i++)
	{
		F[i]=G[i]=INF;
		H[i]=0;
	}
	for (i=1;i<=N+1;i++)
	{
		for (j=i-1;j>=0 && S[i]-S[j]<=DIST;j--)
		{
			if (F[j]+C[i]<F[i])
			{
				F[i]=F[j]+C[i];
				G[i]=G[j]+1;
				H[i]=j;
			}
			else if (F[j]+C[i]==F[i] && G[j]+1<G[i])
			{
				G[i]=G[j]+1;
				H[i]=j;
			}
		}
	}
	A=0;
	for (i=N+1;H[i];i=H[i])
	{
		Ans[++A]=H[i];
	}
	for (i=A;i>=2;i--)
	{
		printf("%d ",S[Ans[i]]);
	}
	printf("%dn",S[Ans[1]]);
}

void dynamic2()
{
	int i,j;
	F[0]=G[0]=0;
	for (i=1;i<=N+1;i++)
	{
		F[i]=G[i]=INF;
		H[i]=0;
	}
	for (i=1;i<=N+1;i++)
	{
		for (j=i-1;j>=0 && S[i]-S[j]<=DIST;j--)
		{
			if (G[j]+1<G[i])
			{
				F[i]=F[j]+C[i];
				G[i]=G[j]+1;
				H[i]=j;

			}
			else if (G[j]+1==G[i] && F[j]+C[i]<F[i])
			{
				F[i]=F[j]+C[i];
				H[i]=j;
			}
		}
	}
	A=0;
	for (i=N+1;H[i];i=H[i])
	{
		Ans[++A]=H[i];
	}
	for (i=A;i>=2;i--)
	{
		printf("%d ",S[Ans[i]]);
	}
	printf("%d",S[Ans[1]]);
}

int main()
{
	init();
	dynamic1();
	dynamic2();
	return 0;
}