#include <cstdio>
#include <cstring>
#include <vector>
#include <set>

#define pb push_back
#define mkp make_pair

using namespace std;

const int NNOD=50001;
const int INF=1000000001;

int nnod,nmuc,i,x,y,cost,vdist[NNOD],dcrt,nodcrt,nvec,add,veccrt,dnew;
int dold,lgmuc;

vector < pair<int, int> > lst[50001];
vector  <pair<int, int> >::iterator it;
set < pair<int,int> > snot;

int main()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);

    scanf ("%d",&nnod); //?
    scanf ("%d",&nmuc);

    for (i=1;i<=nmuc;++i)
    {
        scanf ("%d%d%d",&x,&y,&cost);
        lst[x].pb(mkp(y,cost));
    }

    snot.insert(mkp(0,1));

 //   for (i=2;i<=nnod;++i) snot.insert(mkp(INF,i))

    for (i=2;i<=nnod;++i)
    {
        vdist[i]=INF;
    }

    while (!snot.empty())
    {
        dcrt=snot.begin()->first;
        nodcrt=snot.begin()->second;
        snot.erase(snot.begin());
        vdist[nodcrt]=dcrt;

        nvec=lst[nodcrt].size();
        add=vdist[nodcrt];

        for (it=lst[nodcrt].begin(); it!=lst[nodcrt].end(); ++it)
        {
            veccrt=it->first;
            lgmuc=it->second;

            if (veccrt==nodcrt) continue;

            dnew=add+lgmuc;
            dold=vdist[veccrt];

            if (dnew<dold)
            {
                if (dold!=INF)
                {
                    snot.erase(snot.find(mkp(dold,veccrt)));
                }
                snot.insert(mkp(dnew,veccrt));
                vdist[veccrt]=dnew;

            }
        }

    }

    for (i=2;i<=nnod;++i)
    {
        printf ("%d ",vdist[i]);
    }


    return 0;
}