#include <iostream>
#include <fstream>
using namespace std;
const int N= 100001;
const int M= 250001;
const int INF= 1000000000;
int lst[N],vf[M],c[M],urm[M],n,m,nr,q[N],d[N];
bool inq [N];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

void adauga (int x,int y,int cost)
{
    nr++;
    vf[nr]=y;
    c[nr]=cost;
    urm[nr]=lst[x];
    lst[x]=nr;
}


int main()
{
    int p,u,x,poz,y,cost;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y>>cost;
        adauga(x,y,cost);
    }

    for(int i=1; i<=n; i++)
        d[i]=INF;
    d[1]=0;
    p=0;
    u=1;
    q[u]=1;
    inq[1]=true;
    while(p!=u)
    {
        p++;
        x=q[p];
        inq[x]=false;
        poz=lst[x];
        while(poz!=0)
        {
            y=vf[poz];
            cost=c[poz];
            if(d[x]+cost<d[y])
            {
                d[y]=d[x]+cost;
                if(!inq[y])
                {
                    q[++u]=y;
                    inq[y]=true;
                }
            }
            poz=urm[poz];
        }
    }

    for(int i=2; i<=n; i++)
        out<<d[i]<<" ";

    return 0;
}