#include<fstream>
#include<vector>
#include<queue>
#define oo 200000000
#define pb push_back
#define mp make_pair
#define dim 100004
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int dist[dim],n,m,start,b[dim],p[dim],H[dim],N=0;
bool w[dim];
int x,fiu,tata;

void urcam(int vecinul)
{
    tata=fiu/2;
    while(x<H[tata])
    {
        H[fiu]=H[tata];
        b[fiu]=b[tata];
        int v=b[tata];
        p[v]=fiu;

        fiu=tata;
        tata=tata/2;
    }
    H[fiu]=x;
    b[fiu]=vecinul;
    p[vecinul]=fiu;
}

vector < pair < int, int > > a[dim];

inline void cit()
{
    f>>n>>m;
    int i,y,x,c;
    for(i = 1; i<= m; i ++)
    {
        f>>x>>y>>c;
        a[x].pb(mp(y,c));
    }
}

inline void dij(int i)
{
    int poz;

    for(int j = 1; j <= n; j ++)
        dist[j] = oo;

    dist[i] = 0;
    b[1]=i;

    w[i] = true;
    H[0]=-1;

    H[1]=i;
    N=1;

    while(N>0)
    {
        poz=b[1];//poz=nodul din varf
        x=H[N];
        int v=b[N];
        b[1]=v;
        p[v]=1;
        --N; //stergem nodul din varful heap-ului
        w[poz] = false;

        tata=1;
        fiu=2;
        while(fiu<=N)
        {
            if(fiu<N)
                if(H[fiu]>H[fiu+1])
                    fiu=fiu+1;

            if(x>H[fiu])
            {
                H[tata]=H[fiu];
                b[tata]=b[fiu];
                tata=fiu;
                fiu*=2;
            }
            else
                fiu=N+1;
        }
        H[tata]=x;
        b[tata]=v;
        p[v]=tata;

        for(int j = 0; j < a[poz].size(); ++ j)
        {
            int vecin = a[poz][j].first;
            int cost = a[poz][j].second;
            if(dist[vecin] > dist[poz] + cost)
            {
                x=dist[vecin] = dist[poz] + cost;

                if(w[vecin] == false)
                {
                    ++N;
                    b[N]=vecin;
                    H[N]=x;
                    fiu=N;
                    p[vecin]=N;
                    urcam(vecin);
                }
                else //if(w[vecin] == true)
                {
                    tata=p[vecin];
                    urcam(vecin);
                }

            }//end if(dist[vecin] > dist[poz] + cost)
        }
    }
}

int main()
{
    int i;
    cit();
    dij(1);
    for(i = 2; i <= n; i ++)
       if(dist[i] == oo)
        g<<"0 ";
       else
        g<<dist[i]<<" ";
}