#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 50010;

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

struct mch
{
    int dest,dist;//destinatie si distanta
};

priority_queue< pair<int,int>,vector< pair<int,int> >, greater< pair<int,int> > > heap;
vector<mch> vecin[MAXN];
int d[MAXN];
int n,m;

void citire()
{
    int a,b,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    in >> n >> m;
    for (int i = 1;i <= m;++i)
    {
        in >> a >> b >> c;
        vecin[a].push_back((mch){b,c});
    }
}

void initializare_d()
{
    for (int i = 1;i <= n;++i)
        d[i] = -1;
}

void dijkstra(int s)
{
    int nod;
    //golire_heap
    initializare_d();
    heap.push(make_pair(0,s));
    while (!heap.empty())
    {
        while (!heap.empty() && d[heap.top().second] != -1)
            heap.pop();
        if (heap.empty())
            break;
        nod = heap.top().second;
        d[nod] = heap.top().first;
        for (unsigned int i = 0;i < vecin[nod].size();++i)
            heap.push(make_pair(d[nod] + vecin[nod][i].dist,vecin[nod][i].dest));
    }
}

void afisare()
{
    for (int i = 2;i <= n;++i)
        out << ((d[i] != -1)?d[i]:0) << " ";
}

int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}