#include <bits/stdc++.h>
#define ll long long

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m;
vector<int> G[50001], C[50001];
ll int cost[50001];
const ll int inf=1e15;

struct minHeapNode
{
    int nod;
    ll int cost;
};
minHeapNode H[50001];
int cnt;
int poz[50001];

bool operator<(minHeapNode x, minHeapNode y)
{
    return x.cost<y.cost;
}

void newNode(minHeapNode x)
{
    H[++cnt]=x;
    poz[x.nod]=cnt;
}

void push_up(int i)
{
    while(i/2>=1 && H[i]<H[i/2])
    {
        minHeapNode aux=H[i];
        H[i]=H[i/2];
        H[i/2]=aux;
        poz[H[i].nod]=i;
        poz[H[i/2].nod]=i/2;
        i/=2;
    }
}

void pop()
{
    H[1]=H[cnt];
    cnt--;
    poz[H[1].nod]=1;
    int i=1;
    while(2*i<=cnt)
    {
        int j=2*i;
        if(j+1<=cnt && H[j+1]<H[j])
            j++;
        if(H[i]<H[j])
            return;
        else
        {
            minHeapNode aux=H[i];
            H[i]=H[j];
            H[j]=aux;
            poz[H[i].nod]=i;
            poz[H[j].nod]=j;
            i=j;
        }
    }
}

void Citire()
{
    int i, j, p;
    fin >> n >> m;
    for(int c=0; c<m; c++)
    {
        fin >> i >> j >> p;
        G[i].push_back(j);
        C[i].push_back(p);
    }
}

void Dijkstra(int st)
{
    int i, j, p;
    cost[st]=0;
    newNode(minHeapNode{st, 0});
    for(i=1; i<=n; i++)
        if(i!=st)
        {
            newNode(minHeapNode{i, inf});
            cost[i]=inf;
        }
    while(cnt>0)
    {
        int x=H[1].nod;
        pop();
        for(i=0; i<G[x].size(); i++)
        {
            j=G[x][i];
            p=C[x][i];
            if(cost[x]+p<cost[j])
            {
                cost[j]=cost[x]+p;
                H[poz[j]].cost=cost[j];
                push_up(poz[j]);
            }
        }
    }
    for(i=1; i<=n; i++)
        if(cost[i]==inf)
            cost[i]=0;
}

void Afisare()
{
    int i;
    for(i=2; i<=n; i++)
        fout << cost[i] << " ";
}

int main()
{
    Citire();
    Dijkstra(1);
    Afisare();
    return 0;
}