#include<stdio.h>
#include<queue>
#include<vector>

using namespace std;

#define Nmax 50005
#define inf 0x3f3f3f3f

int N,M,d[Nmax],v[Nmax];

vector < pair<int,int> > l[Nmax];

struct cmp
{
    bool operator()(int a,int b)
    {
        return (d[a] > d[b]);
    }
};

priority_queue <int, vector<int> , cmp> Heap;

void dijkstra()
{
    for(int i=1;i<=N;++i)
        d[i]=inf;
    d[1]=0;
    v[1]=1;
    Heap.push(1);

    int nod;
    for(; !Heap.empty() ;)
        {
        nod=Heap.top();
        v[nod]=1;
        for(int i=0;i<(int)l[nod].size() ;++i)
            if (d[ l[nod][i].first ] > d[nod] + l[nod][i].second)
                {
                d[ l[nod][i].first ] = d[nod] + l[nod][i].second;
                if (!v[ l[nod][i].first ])
                    {
                    v[ l[nod][i].first ]=1;
                    Heap.push( l[nod][i].first );
                    }
                }
        Heap.pop();
        }

    for(int i=2;i<=N;++i)
        if (d[i]!=inf)
            printf("%d ",d[i]);
        else
            printf("0 ");
    printf("\n");
}

void cit();

int main()
{
    cit();
    dijkstra();
    return 0;
}

void cit()
{
    int a,b,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)
        {
        scanf("%d%d%d",&a,&b,&c);
        l[a].push_back( make_pair(b,c) );
        }
}