#include <fstream>
#include <vector>
#include <queue>

using namespace std;
#define Inf 0x3f3f3f

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

struct Edge{
    int v;
    int cost;
};

int n, m;
vector<vector<Edge> > a;
queue<int> q;
int x;
Edge aux;
int d[55000];
bool ok[55000];


int main()
{
    is >> n >> m;
    a.resize(m+1);
    for(int i = 1; i <= m; ++i)
    {
        is >> x;
        is >> aux.v;
        is >> aux.cost;
        a[x].push_back(aux);
    }

    for(int i = 1; i <= n; ++i)
        d[i] = Inf;
    d[1] = 0;
    q.push(1);
    ok[1] = true;

    while(!q.empty())
    {
        x = q.front();
        q.pop();
        ok[x] = false;
        for(vector<Edge>::iterator it = a[x].begin(); it != a[x].end(); ++it)
        {
            int y = it->v;
            int c = it->cost;
            if(d[y] > d[x] + c)
            {
                d[y] = d[x] + c;
                if(!ok[y])
                {
                    q.push(y);
                    ok[y] = true;
                }
            }

        }

    }

    for(int i = 2; i <= n; ++i)
        os << d[i] << ' ';
    is.close();
    os.close();
    return 0;
}