#include<cstdio>

#include<cmath>

using namespace std;

typedef long long LL;

LL cnt[];

int ans[];

int main()

{

        LL n;

        scanf("%lld",&n);

        LL now=;

        int len;

        for(len=;;len++)

        {

                if(n>now) n-=now;

                else break;

                if(len%==) now*=;

        }

        int i=len+>>;

        n--;

        LL tmp=;

        for(int j=;j<i;j++) tmp*=;

        for(int j=;j<i;j++)

        {

                for(int k=(j==);k<=;k++)

                {

                        if(j== && k==) ans[j]=;

                        if(n>=tmp) ans[j]++,n-=tmp;

                        else break;

                }

                tmp/=;

        }

        for(int j=;j<i;j++) printf("%d",ans[j]);

        printf("%d",n);

        if(len%==) printf("%d",n);

        for(int j=i-;j;j--) printf("%d",ans[j]);

}        

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 1001

using namespace std;

int sx[N],sy[N],bx[N],by[N];

int f[][][],cnt[][];

char s[][][];

int dx[]={,,,-};

int dy[]={,,-,};

char c[]={'E','N','S','W'};

int main()

{

    int n,m,k;

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=n;i++) scanf("%d%d",&sx[i],&sy[i]);

    for(int i=;i<=m;i++) scanf("%d%d",&bx[i],&by[i]);

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            if(abs(bx[j]-sx[i])+abs(by[j]-sy[i])<=k) cnt[bx[j]-sx[i]+k][by[j]-sy[i]+k]++;

    memset(f,-,sizeof(f));

    f[][k][k]=;

    for(int h=;h<=k;h++)

        for(int i=;i<=*k;i++)

            for(int j=;j<=*k;j++)

                if(abs(i-k)+abs(j-k)<=h)

                    f[h][i][j]=cnt[i][j]+max(max(f[h-][i-][j],f[h-][i+][j]),max(f[h-][i][j-],f[h-][i][j+]));

    int ans=-;

    for(int i=;i<=*k;i++)

        for(int j=;j<=*k;j++)

            ans=max(ans,f[k][i][j]);

    for(int i=;i<=*k;i++)

        for(int j=;j<=*k;j++)

            if(f[k][i][j]==ans) s[k][i][j]='Z';

    for(int h=k-;h>=;h--)

        for(int i=;i<=*k;i++)

            for(int j=;j<=*k;j++)

                if(abs(i-k)+abs(j-k)<=h)

                    for(int l=;l<;l++)

                        if(s[h+][i+dx[l]][j+dy[l]] && f[h][i][j]+cnt[i+dx[l]][j+dy[l]]==f[h+][i+dx[l]][j+dy[l]])

                            { s[h][i][j]=c[l]; break; }

    printf("%d\n",ans);

    int x=k,y=k;

    for(int h=;h<k;h++)

    {

        putchar(s[h][x][y]);

        for(int l=;l<;l++)

            if(s[h][x][y]==c[l])

            {

                x+=dx[l]; y+=dy[l];

                break;

            }

    }

}

#include<cstdio>

#include<queue>

#include<cmath>

#include<cstring>

#define N 1001

#define M 5001

using namespace std;

int happy[N],cnt[N],n;

int front[N],to[M],nxt[M],val[M],tot;

double dis[N];

bool vis[N];

void add(int u,int v,int w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;

}

bool spfa(double m)

{

    for(int i=1;i<=n;i++) dis[i]=2e9;

    memset(vis,false,sizeof(vis));

    memset(cnt,0,sizeof(cnt));

    queue<int>q;

    vis[1]=true;

    dis[1]=0;

    q.push(1);

    int now;

    while(!q.empty())

    {

        now=q.front();

        q.pop(); vis[now]=false;

        for(int i=front[now];i;i=nxt[i])

            if(dis[to[i]]>dis[now]+m*val[i]-happy[to[i]])

            {

                dis[to[i]]=dis[now]+m*val[i]-happy[to[i]];

                if(!vis[to[i]])

                {

                    vis[to[i]]=true;

                    q.push(to[i]);

                    cnt[to[i]]++;

                    if(cnt[to[i]]>n) return true;

                }

            }

    }

    return false;

}

int main()

{

    int p;

    scanf("%d%d",&n,&p);

    for(int i=1;i<=n;i++) scanf("%d",&happy[i]);

    int u,v,w;

    while(p--)

    {

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

    }

    double l,r=1000,mid;

    while(fabs(l-r)>1e-3)

    {

        mid=(l+r)/2;

        if(spfa(mid)) l=mid;

        else r=mid;

    }

    printf("%.2lf",l);

}