#include <iostream>
#include <fstream>
#include <set>
#include <vector>

using namespace std;

#define INF 30000

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

long int n, m;

struct graph{
    vector<pair<long int,long int> >* adj;
    long int sz;

    graph(const long int& s)
    {
        adj = new vector<pair<long int,long int> >[s];
        sz = s;
    }

    long int size() const
    {
        return sz;
    }

    void insertEdge(const long int& u, const long int& v, const long int& w)
    {
        adj[u].push_back(pair<long int,long int>(w,v));
    }

};

void dijkstra(graph& gr, long int src)
{
    set<pair<long int,long int> > vset;
    vector<long int> dist(gr.size(), INF);

    vset.insert(make_pair(0,src));
    dist[src] = 0;

    while(!vset.empty())
    {
        pair<long int,long int> t = *vset.begin();
        vset.erase(vset.begin());

        long int vert = t.second;

        typedef vector<pair<long int,long int> >::iterator it;
        for(it itt = gr.adj[vert].begin(); itt!=gr.adj[vert].end(); itt++)
        {
            long int w = (*itt).first;
            long int u = (*itt).second;


            if(dist[u] > dist[vert] + w)
            {
                if(dist[u] != INF)
                    vset.erase(vset.find(make_pair(dist[u],u)));
                dist[u] = dist[vert] + w;
                vset.insert(make_pair(dist[u],u));
            }
        }
    }

    for(long int i = 1; i < gr.size(); i++)
        g << dist[i] << ' ';

}

int main()
{
    f >> n >> m;

    graph gr(n);

    for(long int i = 0; i < m; i++)
    {
        long int a, b, c;
        f >> a >> b >> c;
        a--;b--;
        gr.insertEdge(a,b,c);
    }

    dijkstra(gr,0);

    return 0;
}