#include <fstream>
#include <queue>

using namespace std;

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

struct Road
{
    int len, connect;
    bool operator < (const Road other) const
    {
        return len > other.len;
    }
};

priority_queue <Road> pq;

bool visit[50005];
int final[50005];
vector <Road> v[50005];

void Dijkstra()
{
    while(!pq.empty())
    {
        Road start = pq.top();
        int node = start.connect;
        pq.pop();
        if(visit[node] == 0)
        {
            for(int i = 0; i < v[node].size(); i++)
            {
                int length = v[node][i].len + final[node];
                if(length < final[v[node][i].connect] || (final[v[node][i].connect] == 0 && v[node][i].connect != 1))
                {
                    final[v[node][i].connect] = length;
                    pq.push({length, v[node][i].connect});
                }
            }
        }
        visit[node] = 1;
    }

}
int main(void)
{
    int n, m;
    fin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int a;
        Road node;
        fin >> a >> node.connect >> node.len;
        v[a].push_back(node);
    }
    final[1] = 0;
    pq.push({0, 1});
    Dijkstra();
    for(int i = 2; i <= n; i++)
        fout << final[i] <<' ';
}