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

using namespace std;

#define INF 30000

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

int n, m;

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

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

    int size() const
    {
        return sz;
    }

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

};

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

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

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

        int vert = t.second;

        typedef vector<pair<int,int> >::iterator it;
        for(it itt = gr.adj[vert].begin(); itt!=gr.adj[vert].end(); itt++)
        {
            int w = (*itt).first;
            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(int i = 1; i < gr.size(); i++)
        g << dist[i] << ' ';

}

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

    graph gr(n);

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

    dijkstra(gr,0);

    return 0;
}