#include <cstdio>
#include <iostream>
#include <queue>
#include <climits>
#define NMAX 50000+5
#define mp make_pair
#define p pair<int,int>
#define f first
#define s second

using namespace std;

int N,M;
bool c[NMAX];
int D[NMAX];
vector <p> leg[NMAX];

struct comp
{
    bool operator()(int x,int y)
    {
        return D[x]>D[y];
    }
};
priority_queue<int, vector<int>, comp>q;

void djikstra(int nodi)
{
    for(int i=1; i<=N; i++)
        D[i]=INT_MAX;

    D[nodi]=0;
    q.push(nodi);

    while(!q.empty())
    {
        int nod=q.top();
        c[nod]=true;
        for(int i=0;i<leg[nod].size();i++)
        {
            int vec=leg[nod][i].f;
            int len=leg[nod][i].s;
            if(D[nod]+len<D[vec])
            {
                D[vec]=D[nod]+len;
                if(!c[vec])
                {
                    q.push(vec);
                    c[vec]=true;
                }
            }
        }
        q.pop();
    }
}

int main()
{
    freopen("djikstra.in","r",stdin);
    freopen("djikstra.out","w",stdout);
    scanf("%d %d",&N,&M);

    for(int i=1; i<=M; i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        leg[x].push_back(mp(y,z));
    }

    djikstra(1);

    for(int i=2;i<=N;i++)
    {
        printf("%d ",D[i]);
    }

    return 0;
}