#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],nodcrt,add,veccrt,dnew;
int 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)
    {
        vdist[i]=INF;
    }

    while (!snot.empty())
    {
        add=snot.begin()->first;
        nodcrt=snot.begin()->second;
        snot.erase(snot.begin());

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

            if (veccrt==nodcrt) continue;

            dnew=add+lgmuc;

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

            }
        }

    }

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


    return 0;
}