try dijkstra to solve this problem. pass all tests found.
but meet WA#1. try to review code several times but cann't figure out why.
code is here if you found why pls reply.tks
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERT_NUM 100
#define BIT_SET(a, b) (a|=b)
#define BIT_RESET(a, b) (a&=(~b))
#define BIT_TEST(a, b) (0!=(a&b))

#define EDGE_TAG_PROCED 0x01

typedef struct tagEDGE{
    struct tagEDGE *pstNext;
    int iEnd;
    long iWeight;
    unsigned char ucFlag;
}EDGE_S;

#define VERT_TAG_PROCED 0x01
typedef struct tagVERT{
    EDGE_S *pstEdge;
    long iPathLen;
    int iPathNodeNum;
    int aiPathNode[MAX_VERT_NUM];
    unsigned char ucFlag;
}VERT_S;

void addEdgeNode(VERT_S *pstVert, int iFrom, int iTo, long iWeight)
{
    EDGE_S *pstEdge = NULL;

    pstEdge = pstVert[iFrom].pstEdge;
    while (NULL != pstEdge)
    {
        if (iTo == pstEdge->iEnd)
        {
            if (pstEdge->iWeight > iWeight)
            {
                pstEdge->iWeight = iWeight;
            }
            return ;
        }
        pstEdge = pstEdge->pstNext;
    }

    pstEdge = malloc(sizeof(EDGE_S));
    if (NULL != pstEdge)
    {
        memset(pstEdge, 0, sizeof(EDGE_S));
        pstEdge->iEnd    = iTo;
        pstEdge->iWeight = iWeight;
        if (NULL == pstVert[iFrom].pstEdge)
        {
            pstVert[iFrom].pstEdge = pstEdge;
        }
        else
        {
            pstEdge->pstNext = pstVert[iFrom].pstEdge;
            pstVert[iFrom].pstEdge = pstEdge;
        }
    }

    return ;
}

void AddEdge(VERT_S *pstVert, int iFrom, int iTo, long iWeight)
{
    addEdgeNode(pstVert, iFrom, iTo, iWeight);
    addEdgeNode(pstVert, iTo, iFrom, iWeight);

    return ;
}

void init(VERT_S *pstVert)
{
    int i=0;
    memset(pstVert, 0, MAX_VERT_NUM*sizeof(VERT_S));
    for (i=0; i<MAX_VERT_NUM; i++)
    {
        pstVert[i].iPathLen = LONG_MAX;
    }

    return ;
}

void relax(VERT_S *pstVert, int iFrom, int iTo, EDGE_S *pstEdge)
{
    VERT_S *pstFromVert = NULL, *pstToVert = NULL;

    pstFromVert = &pstVert[iFrom];
    pstToVert   = &pstVert[iTo];

    if (pstToVert->iPathLen > pstFromVert->iPathLen + pstEdge->iWeight)
    {
        pstToVert->iPathLen = pstFromVert->iPathLen + pstEdge->iWeight;
        pstToVert->iPathNodeNum = pstFromVert->iPathNodeNum+1;
        memcpy(pstToVert->aiPathNode,
               pstFromVert->aiPathNode,
               sizeof(pstFromVert->aiPathNode));
        pstToVert->aiPathNode[pstFromVert->iPathNodeNum] = iTo;
    }

    return ;
}

int foundMinVert(VERT_S *pstVert)
{
    int iMinVert = -1, i=0;

    for (i=0; i<MAX_VERT_NUM; i++)
    {
        if (!BIT_TEST(pstVert[i].ucFlag, VERT_TAG_PROCED) &&
            (LONG_MAX > pstVert[i].iPathLen))
        {
            if (-1 == iMinVert)
            {
                iMinVert = i;
            }
            else
            {
                if (pstVert[i].iPathLen < pstVert[iMinVert].iPathLen)
                {
                    iMinVert = i;
                }
            }
        }
    }

    return iMinVert;
}

void calcShortPath(VERT_S *pstVert, int iSource)
{
    int i=0, iFrom=0, iTo=0, iMinVert = -1;
    VERT_S *pstCurVert = NULL, *pstEndVert=NULL;
    EDGE_S *pstEdge = NULL;

    pstCurVert = &pstVert[iSource];
    pstCurVert->iPathLen = 0;
    BIT_SET(pstCurVert->ucFlag, VERT_TAG_PROCED);
    iFrom = iSource;
    pstCurVert->iPathNodeNum = 1;
    pstCurVert->aiPathNode[0] = iSource;
    for (i=0; i<MAX_VERT_NUM; i++)
    {
        pstEdge = pstCurVert->pstEdge;
        while (NULL != pstEdge)
        {
            iTo = pstEdge->iEnd;
            if ((!BIT_TEST(pstVert[iTo].ucFlag, VERT_TAG_PROCED)) &&
                (!BIT_TEST(pstEdge->ucFlag, EDGE_TAG_PROCED)))
            {
                relax(pstVert, iFrom, iTo, pstEdge);
            }
            pstEdge = pstEdge->pstNext;
        }
        iFrom = foundMinVert(pstVert);
        if (-1 != iFrom)
        {
            BIT_SET(pstVert[iFrom].ucFlag, VERT_TAG_PROCED);
            pstCurVert = &pstVert[iFrom];
        }
        else
        {
            break;
        }
    }

    return ;
}

void reset(VERT_S *pstVert)
{
    int i=0;

    for (i=0; i<MAX_VERT_NUM; i++)
    {
        pstVert[i].ucFlag = 0;
        pstVert[i].iPathLen = LONG_MAX;
        pstVert[i].iPathNodeNum = 0;
        memset(pstVert[i].aiPathNode, 0, sizeof(pstVert[i].aiPathNode));
    }

    return ;
}

void setEdgeNodeFlag(VERT_S *pstVert, int iFrom, int iTo, unsigned char ucFlag)
{
    EDGE_S *pstEdge = NULL;

    pstEdge = pstVert[iFrom].pstEdge;
    while (NULL != pstEdge)
    {
        if (iTo == pstEdge->iEnd)
        {
            BIT_SET(pstEdge->ucFlag, ucFlag);
        }
        pstEdge = pstEdge->pstNext;
    }

    return ;
}

void setEdgeFlag(VERT_S *pstVert, int iFrom, int iTo, unsigned char ucFlag)
{
    setEdgeNodeFlag(pstVert, iFrom, iTo, ucFlag);
    setEdgeNodeFlag(pstVert, iTo, iFrom, ucFlag);

    return ;
}

void resetEdgeNodeFlag(VERT_S *pstVert, int iFrom, int iTo, unsigned char ucFlag)
{
    EDGE_S *pstEdge = NULL;

    pstEdge = pstVert[iFrom].pstEdge;
    while (NULL != pstEdge)
    {
        if (iTo == pstEdge->iEnd)
        {
            BIT_RESET(pstEdge->ucFlag, ucFlag);
        }
        pstEdge = pstEdge->pstNext;
    }

    return ;
}

void resetEdgeFlag(VERT_S *pstVert, int iFrom, int iTo, unsigned char ucFlag)
{
    resetEdgeNodeFlag(pstVert, iFrom, iTo, ucFlag);
    resetEdgeNodeFlag(pstVert, iTo, iFrom, ucFlag);

    return ;
}

void freeall(VERT_S *pstVert)
{
    int i=0;
    EDGE_S *pstEdge = NULL, *pstFree = NULL;

    for (i=0; i<MAX_VERT_NUM; i++)
    {
        pstEdge = pstVert[i].pstEdge;
        while (NULL != pstEdge)
        {
            pstFree = pstEdge;
            pstEdge = pstEdge->pstNext;
            free(pstFree);
        }
    }

    return ;
}

int main()
{
    int iCross=0, iRoad = 0;
    int i=0, iFrom=0, iTo=0,  j=0;
    long iWeight=0;
    VERT_S astVert[MAX_VERT_NUM];
    EDGE_S *pstEdge = NULL;
    int  iMinPathNode = 0;
    long iMinPathLen = -1;
    int aiMinPath[MAX_VERT_NUM];

    scanf("%d", &iCross);
    while ((-1 != iCross))
    {
        scanf("%d", &iRoad);
        init(astVert);
        iMinPathNode = 0;
        iMinPathLen = LONG_MAX;
        memset(aiMinPath, 0, sizeof(aiMinPath));
        for (i=0; i<iRoad; i++)
        {
            scanf("%d %d %ld", &iFrom, &iTo, &iWeight);
            AddEdge(astVert, iFrom-1, iTo-1, iWeight);
        }

        for (i=0; i<MAX_VERT_NUM; i++)
        {
            iFrom = i;
            pstEdge = astVert[i].pstEdge;
            while (NULL != pstEdge)
            {
                iTo = pstEdge->iEnd;
                setEdgeFlag(astVert, iFrom, iTo, EDGE_TAG_PROCED);
                calcShortPath(astVert, iFrom);

                if (iMinPathLen >
                    (astVert[iTo].iPathLen + pstEdge->iWeight))
                {
                    iMinPathLen = astVert[iTo].iPathLen + pstEdge->iWeight ;
                    iMinPathNode = astVert[iTo].iPathNodeNum;
                    memcpy(aiMinPath, astVert[iTo].aiPathNode, sizeof(aiMinPath));
                }

                resetEdgeFlag(astVert, iFrom, iTo, EDGE_TAG_PROCED);
                reset(astVert);
                pstEdge = pstEdge->pstNext;
            }
        }

        freeall(astVert);

        if (LONG_MAX == iMinPathLen)
        {
            printf("No solution.\r\n");
        }
        else
        {
            for (i=0; i<iMinPathNode; i++)
            {
                printf("%d ", aiMinPath[i]+1);
            }
            printf("\r\n");
        }

        scanf("%d", &iCross);
    }//while

    return 0;
}